Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,957
questions
26
votes
1
answer
2k
views
Consequences of Complete problems for NP intersects coNP
What are the consequences of having complete problems in $NP\cap coNP$?
- 3,280
65
votes
11
answers
5k
views
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
- 1,459
24
votes
3
answers
1k
views
Graph Isomorphism and hidden subgroups
I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
- 31.9k
35
votes
4
answers
989
views
Correspondence between complexity classes and logic
I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, ...
- 863
8
votes
3
answers
3k
views
Is Deolalikar's 2010 proof that $P \ne NP$ correct?
There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof.
So ... is the proof correct or not ? (Please only answer this if you ...
- 863
21
votes
3
answers
551
views
space-bounded TMs and oracles
In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).
Is such a ...
- 433
15
votes
2
answers
1k
views
What is the following variation on Set Cover known as?
What is the following variation on set cover known as?
Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in ...
- 356