Skip to main content
Niel de Beaudrap's user avatar
Niel de Beaudrap's user avatar
Niel de Beaudrap's user avatar
Niel de Beaudrap
  • Member for 13 years, 10 months
  • Last seen more than a month ago
  • Oxford, United Kingdom
37 votes

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

28 votes
Accepted

Consequences of NP=PSPACE

24 votes

What is the quantum computational model?

20 votes

Consequences of $SAT \in BQP$

19 votes
Accepted

A Notion of Monotone Quantum Circuits

18 votes

Difference between infinite state machines and turing machines

17 votes

A good reference for complexity class operators?

16 votes

Computation beyond unitary matrices

15 votes

A possibly new representation of DAGs

15 votes
Accepted

Duality computers

14 votes
Accepted

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

13 votes
Accepted

Is there a backup/replacement for the Complexity Zoo?

12 votes

Bounded depth probability distributions

12 votes

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

11 votes

Natural notion for computational hardness

11 votes
Accepted

Why is shifting bits different from shifting qubits?

11 votes

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

11 votes

Differences between Quantum Computing and Parallelism

10 votes

P with integer factorization oracle

10 votes

Is any QMA-intermediate problem known?

9 votes
Accepted

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

9 votes
Accepted

When does randomization stops helping within PSPACE

9 votes
Accepted

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

8 votes

A graph parameter possibly related to treewidth

7 votes
Accepted

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

7 votes
Accepted

Efficient representation of set of partial order

7 votes
Accepted

Finding all cycles

7 votes
Accepted

Quantum Computation - Postulates of QM

7 votes
Accepted

How powerful is exact "quantum" computing if you suspend unitarity?

7 votes
Accepted

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