User Niel de Beaudrap

37 votes

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

answered Mar 7, 2011 at 15:13

28 votes

Accepted

Consequences of NP=PSPACE

answered Feb 13, 2014 at 20:02

24 votes

What is the quantum computational model?

answered Aug 24, 2010 at 12:34

20 votes

Consequences of $SAT \in BQP$

answered Apr 18, 2011 at 14:51

19 votes

Accepted

A Notion of Monotone Quantum Circuits

answered Sep 18, 2012 at 23:11

18 votes

Difference between infinite state machines and turing machines

answered Jan 22, 2014 at 20:38

17 votes

A good reference for complexity class operators?

answered Mar 18, 2014 at 16:02

16 votes

Computation beyond unitary matrices

answered Jul 28, 2011 at 15:31

15 votes

A possibly new representation of DAGs

answered Apr 3, 2011 at 16:47

15 votes

Accepted

Duality computers

answered Apr 13, 2011 at 16:36

14 votes

Accepted

Is there notation for converting a multi-set to a set?

answered Dec 19, 2014 at 19:58

13 votes

Accepted

Is there a backup/replacement for the Complexity Zoo?

answered Jul 25, 2012 at 15:39

12 votes

Bounded depth probability distributions

answered Dec 9, 2012 at 20:46

12 votes

Why does randomness have stronger effect on reductions than on algorithms?

answered Dec 28, 2012 at 10:28

11 votes

Natural notion for computational hardness

answered Feb 17, 2011 at 13:53

11 votes

Accepted

Why is shifting bits different from shifting qubits?

answered Oct 24, 2014 at 18:35

11 votes

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

answered Apr 17, 2015 at 0:05

11 votes

Differences between Quantum Computing and Parallelism

answered Dec 20, 2013 at 17:01

10 votes

P with integer factorization oracle

answered Mar 31, 2014 at 15:59

9 votes

Accepted

Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?

answered Oct 18, 2012 at 16:42

9 votes

Is any QMA-intermediate problem known?

answered Jul 25, 2014 at 15:59

9 votes

Accepted

When does randomization stops helping within PSPACE

answered May 1, 2015 at 5:36

9 votes

Accepted

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

answered Feb 20, 2012 at 2:37

8 votes

A graph parameter possibly related to treewidth

answered Sep 26, 2012 at 17:37

7 votes

Accepted

why is a Turing machine defined as a 5-tuple?

answered Aug 9, 2012 at 19:19

7 votes

Accepted

Efficient representation of set of partial order

answered Mar 24, 2013 at 3:31

7 votes

Accepted

Finding all cycles

answered Aug 23, 2011 at 17:40

7 votes

Accepted

Quantum Computation - Postulates of QM

answered Sep 9, 2010 at 12:30

7 votes

Accepted

Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

answered Dec 11, 2014 at 8:01

6 votes

What complexity issues are there in considering quantum algorithms with infinite gate-sets?

answered Apr 28, 2014 at 1:19

Stack Exchange Network

55 Answers

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

Consequences of NP=PSPACE

What is the quantum computational model?

Consequences of $SAT \in BQP$

A Notion of Monotone Quantum Circuits

Difference between infinite state machines and turing machines

A good reference for complexity class operators?

Computation beyond unitary matrices

A possibly new representation of DAGs

Duality computers

Is there notation for converting a multi-set to a set?

Is there a backup/replacement for the Complexity Zoo?

Bounded depth probability distributions

Why does randomness have stronger effect on reductions than on algorithms?

Natural notion for computational hardness

Why is shifting bits different from shifting qubits?

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Differences between Quantum Computing and Parallelism

P with integer factorization oracle

Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?

Is any QMA-intermediate problem known?

When does randomization stops helping within PSPACE

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

A graph parameter possibly related to treewidth

why is a Turing machine defined as a 5-tuple?

Efficient representation of set of partial order

Finding all cycles

Quantum Computation - Postulates of QM

Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

What complexity issues are there in considering quantum algorithms with infinite gate-sets?