Niel de Beaudrap
  • Member for 11 years, 5 months
  • Last seen this week
  • Oxford, United Kingdom
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
37 votes

It does matter, because there is more at stake than whether or not we can find solutions. Also of interest is whether we can verify solutions. Other qualitiative distinctions can be made between the ...

View answer
Consequences of NP=PSPACE
Accepted answer
28 votes

If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply: $\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single ...

View answer
What is the quantum computational model?
24 votes

I'll echo Martin Schwartz's recommendation of Nielsen & Chaung as the standard reference; there are many others as well. Research in the field prefers to consider uniform families of quantum ...

View answer
Consequences of $SAT \in BQP$
19 votes

Scott Aaronson was often fond of pointing out (and probably still is fond of pointing out, assuming he hasn't gotten tired of doing so) that physical processes do not always find the global minimum of ...

View answer
Difference between infinite state machines and turing machines
18 votes

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like. Make the initial state accept if the empty ...

View answer
A good reference for complexity class operators?
17 votes

As an introductory reference to the notion of a complexity operator (and demonstrating some applications of the idea), the best I have found so far is D. Kozen, Theory of Computation (Springer ...

View answer
A Notion of Monotone Quantum Circuits
Accepted answer
17 votes

You're really asking two different questions and hoping that there is a single response which answers both: (1) What natural notions of quantum monotone circuits are there? (2) What would a lattice-...

View answer
Computation beyond unitary matrices
16 votes

In a pure mathematical sense, you could in principle create models of computation using any sort of recursively composable structure, so long as you can describe how it represents a transformation of ...

View answer
A possibly new representation of DAGs
15 votes

[Revised.] I think that there has been a little confusion about what I was referring to in my original answer. I am revising it in order to better describe the result. Note that your representation ...

View answer
Is there notation for converting a multi-set to a set?
Accepted answer
14 votes

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here. Multisets are an awkward case of a perfectly natural mathematical ...

View answer
Duality computers
Accepted answer
14 votes

Summary. All of these papers misunderstand the notion of quantum superpositions and interference, and lead to analyses which do not conserve probability (i.e. in which the probabilities of ...

View answer
Is there a backup/replacement for the Complexity Zoo?
Accepted answer
13 votes

I cannot remark on whether the Zoo has a continuous existence on the web or elsewhere. However, there are still some proto-Zoo and Zoo-derived resources available on the web. There seems to be a copy ...

View answer
Why does randomness have stronger effect on reductions than on algorithms?
12 votes

One reason why it might seem strange to you, that we seem to think there is more apparent (or conjectured) power in the randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$ than the comparable ...

View answer
Bounded depth probability distributions
12 votes

Short answer. For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the ...

View answer
Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?
11 votes

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) show that the nondeterministic time ...

View answer
Why is shifting bits different from shifting qubits?
Accepted answer
11 votes

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special ...

View answer
Differences between Quantum Computing and Parallelism
11 votes

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number ...

View answer
Natural notion for computational hardness
11 votes

Just what makes growth rates such as O(n²) artificial — just the fact that it isn't one specific monotonic function? Or is it the fact that it's a family of functions in itself, and not just some ...

View answer
P with integer factorization oracle
10 votes

Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap ...

View answer
When does randomization stops helping within PSPACE
Accepted answer
9 votes

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ ...

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

Note that Gödel's Incompleteness Theorems are the following statements: Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither ...

View answer
Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?
Accepted answer
9 votes

I'm happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete. We can actually reduce this ...

View answer
Is any QMA-intermediate problem known?
8 votes

An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract: In this work we ...

View answer
A graph parameter possibly related to treewidth
8 votes

Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer. In your process of adding vertices, define a partial ...

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

No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why. The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex ...

View answer
Efficient representation of set of partial order
Accepted answer
7 votes

Restrictions on pre-orders You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it ...

View answer
why is a Turing machine defined as a 5-tuple?
Accepted answer
7 votes

Short meta preamble — Despite my misgivings (in particular, despite the comment on meta, I don't really think that this question is parallel to the question of why one should define topologies ...

View answer
Finding all cycles
Accepted answer
7 votes

If all that you want to do is count the number of cycles, you can do this with 2|S| bits (plus change) worth of space. It seems unlikely that you will be able to do much better unless S or f have some ...

View answer
Quantum Computation - Postulates of QM
Accepted answer
7 votes

I don't know if this is an "explanation", but hopefully it is a useful "description". More generally than projective measurements, one always measures an operator. (A projector is a special case of ...

View answer
The complexity of decomposing a bi-stochastic matrix
Accepted answer
6 votes

Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using $O(\max\{n^{d+2},n^4\})$ operations over the reals for ...

View answer