awarded
awarded
awarded
awarded
Loading…
revised
Complexity of eigenvalue problem
added 30 characters in body
Loading…
Loading…
comment
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
Interesting, could you provide a reference for $PH^{\#P}$ and the problem of its collapse, please?
revised
What are consequences of the collapse of CH?
added 10 characters in body
Loading…
comment
What are consequences of the collapse of CH?
It does not. The answer you quoted says that the collapse of CH is closely related to another problem with constant-depth threshold circuits. But it does not clarify the relation. According to the complexity zoo $TC^0=CN^1$ imples $CH=PSPACE$ which in turn implies the collapse of $CH$. Thus, constant-depth threshold circuits provide a sufficient condition for the collapse of $CH$, not a consequence.
revised
If P = NP were true, would quantum computers be useful?
added 2 characters in body
Loading…
revised
What are consequences of the collapse of CH?
added 4 characters in body
Loading…
awarded
revised
What are consequences of the collapse of CH?
added 9 characters in body
Loading…
awarded
revised
What are consequences of the collapse of CH?
added 2 characters in body
Loading…
Loading…
comment
Probabilistic and quantum analog of $FP$ and $FNP$?
@Huck Bennett - I don't understand your criticism: computing functions is usual in everyday math, and indeed your laptop not only decides problems but does also compute functions. Considering only decision problems limits our view. On the other hand, if men had had considered only simplest things, we wouldn't have had computers and not even wheels.
comment
Probabilistic and quantum analog of $FP$ and $FNP$?
@Huck Bennett - Do we need motivations for such a natural generalisation of function problem classes? A function problem is a very natural and well-known notion in computational complexity. It is thus very straightforward to ask what are the function problems solved by probabilistic or quantum Turing machines. If we ask similar questions for decision problems, why not for function problems?
comment
Probabilistic and quantum analog of $FP$ and $FNP$?
@usul - Thanks for pointing out the reference in the complexity zoo. Nevertheless, the only relation I found there is an oracle separation between FBQP (quantum analog of FP) and the polynomial local search (PLS).