Most Popular
1500 questions
25
votes
2 answers
Computational complexity of quantum optics
In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:
MY question is three-fold:
Nine years later, can the last cell be filled…
Chris Ferrie
- 503
- 3
- 8
25
votes
3 answers
Complexity of "is a graph a product"
This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate.
There are various graph products, and I'm interested in any of them here. What…
Max
- 1,561
- 11
- 19
25
votes
2 answers
Computational complexity of counting induced subgraphs which admit perfect matchings
Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ restricted to the vertex set $S$ admits a perfect…
h.a
- 523
- 3
- 9
25
votes
11 answers
Example where equivalence is easy but finding class representative is hard
Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent if they are anagrams of each other.
I am…
Martin Pál
- 591
- 3
- 8
24
votes
4 answers
What is the fastest way to check for set inclusion?
Given $n$ subsets $S_1,\ldots,S_n$ of $\{1,\ldots,d\}$.
Check whether there are sets $S_i,S_j$ with $S_i \subsetneq S_j$. (If so, find an example, if not, simply say "no")
The trivial solution to this problem goes through all pairs of sets and…
Karl
- 243
- 1
- 5
24
votes
2 answers
What evidence do we have for (and against) Unique Games Conjecture?
Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory.
What evidence do we have for it? What evidence do we have against it?
Kaveh
- 21,577
- 8
- 82
- 183
24
votes
2 answers
Is there an expressiveness hierarchy for type systems?
Inspired by the extensive hierarchies present in complexity theory, I wondered if such hierarchies were also present for type systems. However, the two examples I've found so far are both more like checklists (with orthogonal features) rather than…
Alex ten Brink
- 4,680
- 25
- 48
24
votes
2 answers
Relation between hardness of recognition of a graph class and forbidden subgraph characterization
I'm considering graph classes that can be characterized by forbidden subgraphs.
If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm (one can just use brute force). But an infinite…
Vinicius dos Santos
- 1,868
- 12
- 21
24
votes
2 answers
What is the big version of NC?
$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$, $k$. My question is if there is an analogous…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
24
votes
4 answers
Survey on #P and/or counting problems
Can anyone suggest a good and recent survey on counting problems and/or problems that are #P.
Tayfun Pay
- 2,598
- 2
- 18
- 45
24
votes
1 answer
For which k is PLANAR NAE k-SAT in P?
The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth assignment of the variables such that each clause…
Florent Foucaud
- 2,153
- 12
- 27
24
votes
2 answers
Space efficient "industrial" unbalanced expanders
I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-expander if for any $S \subset A$ of size at most $k$,…
Piotr
- 971
- 7
- 15
24
votes
1 answer
Reconstruction Conjecture and Partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature, I found that the following classes of graphs are…
Shiva Kintali
- 10,578
- 41
- 74
24
votes
1 answer
Where is the proof that Coq + Excluded Middle is consistent
I've seen (and heard) it claimed that it is safe to add the classical axiom of excluded middle to Coq, but I can not seem to find a paper supporting this claim. The papers I see listed on the Coq wiki about excluded middle are showing inconsistency…
Mark Reitblatt
- 1,690
- 15
- 20
24
votes
12 answers
What are some algorithms where space complexity tends to be the limiting factor in practice?
Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? It puts a hard upper bound on what you can do,…
Adam Tolnay
- 411
- 3
- 5