Most Popular
1500 questions
31
votes
6 answers
Empirical results in CS papers
I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific…
toto
- 413
- 3
- 5
31
votes
3 answers
Is there a result in computability theory that does not relativize?
I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that
Our axiomatization has its limit: it cannot prove any results in computability
theory that fail to relativize to oracle…
Anonymous
- 4,041
- 19
- 43
31
votes
3 answers
coNP certificate for Graph Isomorphism
It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP certificates of GI. Any conjectures that imply $GI \in coNP$…
Shiva Kintali
- 10,578
- 41
- 74
31
votes
4 answers
What is the most powerful kind of parser?
As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of grammar, and I'm not interested in hacking up my…
Paul Biggar
- 420
- 4
- 8
31
votes
5 answers
what is easy for minor-excluded graphs?
Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded graphs?
Update 10/24
It seems to follow Grohe's…
Yaroslav Bulatov
- 4,701
- 1
- 25
- 39
31
votes
1 answer
Refereed games with uncorrelated semi-private coins
I was (and still am) really interested in the answer to this question, because this is an interesting variation on the complexity of games which hasn't been resolved, so I offered a bounty. I thought the original question was very likely too hard,…
Peter Shor
- 24,763
- 4
- 93
- 133
31
votes
1 answer
Can graph isomorphism be decided with square root bounded nondeterminism?
Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those languages that are accepted by some…
András Salamon
- 19,000
- 3
- 64
- 150
31
votes
3 answers
How many instances of 3-SAT are satisfiable?
Consider the 3-SAT problem on n variables. The number of possible distinct clauses is:
$$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$
The number of problem instances is the number of all subsets of the set of possible…
Antonio Valerio Miceli-Barone
- 2,111
- 15
- 21
31
votes
4 answers
Consequences of NP=PSPACE
What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones.
In particular, would it have any consequences on the lower classes?
Denis
- 8,843
- 28
- 55
31
votes
16 answers
Hard-looking algorithmic problems made easy by theorems
I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only.
(2) On the other hand, it becomes easy, if you know…
Andras Farago
- 11,396
- 37
- 70
31
votes
3 answers
Is it NP-hard to play international draughts correctly?
Is the following problem NP-hard?
Given a board configuration for $n\times n$ international draughts, find a single legal move.
The corresponding problem for $n\times n$ American checkers (aka English draughts) is trivially solvable in polynomial…
Jeffε
- 23,129
- 10
- 96
- 163
31
votes
2 answers
Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?
Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?
I realized that I have encountered almost all variants of this question with different conditions about the relationship between i, j, and k, but not this…
Cem Say
- 823
- 7
- 11
31
votes
2 answers
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
txwikinger
- 803
- 1
- 11
- 18
31
votes
5 answers
Verifying unique solutions of SAT
Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ?
What is the complexity of this problem ? (It most surely is in NP, but is it also NP-hard…
J--
- 411
- 4
- 3
31
votes
5 answers
Is there a natural problem on the naturals that is NP-complete?
Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there any natural problems, i.e. ones that do not use…
domotorp
- 13,931
- 37
- 93