user avatar
user avatar
user avatar
Niel de Beaudrap
  • Member for 10 years, 1 month
  • Last seen more than a month ago
  • Oxford, United Kingdom
36 votes

How can I verify a solution to Travelling Salesman Problem in polynomial time?

34 votes
Accepted

NP-Hard problems that are not in NP but decidable

22 votes
Accepted

Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

22 votes
Accepted

How hard is finding the discrete logarithm?

19 votes

Proving P = NP without mathematical statements / computer program

17 votes

Is Morse code without spaces uniquely decipherable?

17 votes
Accepted

Are regular languages closed under sort (Parikh image)?

16 votes

Flaw in my NP = CoNP Proof?

15 votes

Does $NP^{NP}=NP$?

14 votes

What is the difference between quantum TM and nondetermistic TM?

14 votes

Data Structure for Set Intersection?

12 votes

Does a never-halting machine always loop?

12 votes
Accepted

A "natural" decidable problem not in $\mathsf{NP}$?

11 votes

How to prove a problem is NOT NP-Complete?

10 votes

References on comparison between quantum computers and Turing machines

8 votes
Accepted

Origin of quantum complexity theory

8 votes
Accepted

Are randomized algorithms constructive?

8 votes

Finding shortest and longest paths between two vertices in a DAG

7 votes
Accepted

Count unique increasing subsequences of length 3 in $O(n\log n)$

7 votes
Accepted

Quantum algorithms and quantum computation

7 votes
Accepted

Time complexity version of the Church-Turing Thesis

6 votes
Accepted

Why does NTIME consider the length of the longest computation?

5 votes
Accepted

Help need to learn Quantum Computation and Information

5 votes

Finding the greatest $k$ numbers with a certainty of $p$

5 votes
Accepted

Why $\theta/2$ in common qubit representation?

5 votes

Is this data structure a hypertree or they are just isomorphic trees?

5 votes
Accepted

Given a tree, find a vertex which maximizes the minimum distance to any leaf

4 votes

How can one byte hold 256 possibilities?

4 votes
Accepted

Controlled NOT gate a type of measurement?

3 votes

Quantum computing 'amplitudes'