Most Popular
1500 questions
17
votes
1 answer
List of (unsolved) complexity problems arising from PL
What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time complexity of Hindley-Milner type inference" or "the…
xrq
- 1,175
- 6
- 17
17
votes
0 answers
Using Dependent Type Theory for Categories that are not LCCC
I have recently been working with polynomial functors and monads based mostly on Gambino-Kock. There they define polynomial functors in a Locally Cartesian Closed Category (LCCC) and extensively use dependent type theory to define constructions on…
Max New
- 1,675
- 9
- 24
17
votes
1 answer
What is the complexity of this graph problem?
Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that
for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and
the size of $A$ is minimum.
That is, we are looking for a cluster, in…
Andras Farago
- 11,396
- 37
- 70
17
votes
2 answers
Algorithms for set packing
There seems to be much work, for some NP-Hard problems, on developing fast exponential time exact algorithms (i.e., results of the form: Algorithm A solves problem $x$ in O(c^n) time, with c small). There seems to be a fair amount of work along…
Travis Service
- 902
- 7
- 14
17
votes
1 answer
Example demonstrating the power of non-deterministic circuits
A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit…
Gustav Nordh
- 1,047
- 8
- 16
17
votes
0 answers
Intermediate problems between PSPACE and EXPTIME
Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves.
Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, and resisting all efforts to be proved complete for…
Denis
- 8,843
- 28
- 55
17
votes
1 answer
How not to compute the smallest circle enclosing a finite set of circles
Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of Matoušek, Sharir and Welzl [1] to find a basis $B$ of…
Robin Houston
- 761
- 4
- 10
17
votes
2 answers
Is intersection of $k \ge 3$ graphic matroids in P?
It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.
A special case of a problem I am working on can be…
Matej Konecny
- 173
- 4
17
votes
1 answer
Quadratic relationship between nondeterministic and deterministic space?
Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades.
Suppose we approach the problem from the other end.
For…
András Salamon
- 19,000
- 3
- 64
- 150
17
votes
1 answer
How to cite Babai's new graph isomorphism result?
Recently, Babai has published a paper on STOC 2016 claiming that graph isomorphism can be solved in quasipolynomial time.
In the beginning of 2017, Babai retracted the quasipolynomial claim due to some serious mistakes found by Harald Helfgott. As…
Nobo Dy
- 195
- 3
17
votes
2 answers
A reference for a "more algebraic" approach to pushdown automata and CFLs?
In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly mathematical theory of context-free languages".…
Jára Cimrman
- 464
- 2
- 8
17
votes
1 answer
How can non-terminating $\lambda$-terms be turned into fixed-point combinators?
I've been thinking about these questions:
Is there a typed lambda calculus which is consistent and Turing complete?
https://cs.stackexchange.com/questions/65003/if-%CE%BB-x-x-x-has-a-type-then-is-the-type-system-inconsistent
and there are already…
cody
- 13,861
- 1
- 49
- 103
17
votes
3 answers
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the rectangles using minimum number of colors such that…
Soumitra
- 193
- 6
17
votes
3 answers
Formal Semantics of Programming Languages
I'm new to programming languages theory and I'm seeking for a good resource on a resource for formal semantics of programming languages. Specifically looking for structural operational semantics. I got some book recommendations. But I'm looking…
systemsfault
- 273
- 1
- 5
17
votes
2 answers
How is Lambda Calculus a specific type of Term Writing system?
Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda Calculus.
When John McCarthy created Lisp - he based it on the Lambda…
hawkeye
- 2,581
- 1
- 18
- 34