9
votes
3answers
331 views

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
1
vote
0answers
167 views

Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed? More precisely, suppose that for any $M$ accepting $$ \text{coBHP}=\{\langle ...
9
votes
4answers
2k views

Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only. When I learnt to the topic of relativization ...
1
vote
0answers
1k views

Quantum computation implications of (P vs NP) [duplicate]

Possible Duplicate: What impact would P!=NP have on the characterization of BQP? Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that ...
11
votes
2answers
2k views

What impact would P!=NP have on the characterization of BQP?

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
23
votes
2answers
1k views

Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which is guaranteed to run in polynomial time, can we computably find such a polynomial? In other words, is there a computable function $e\mapsto p_e$, ...