Skip to main content
dkaeae's user avatar
dkaeae's user avatar
dkaeae's user avatar
dkaeae
  • Member for 7 years, 2 months
  • Last seen more than 1 year ago
  • Germany
23 votes
Accepted

If graph isomorphism is in P, is then P = NP?

13 votes

Show that there are infinitely more problems than we will ever be able to compute

11 votes
Accepted

Is "Reachable Object" really an NP-complete problem?

10 votes
Accepted

Can you prevent a man in the middle from reading the message?

9 votes
Accepted

How are problems classified in Complexity Theory?

8 votes

Are "of the order of n" and "Big O" the same thing?

8 votes

Intuition behind eigenvalues of an adjacency matrix

6 votes
Accepted

Halting problem in EXP-complete

5 votes

Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

5 votes
Accepted

What publication first introduced the concept of a non-deterministic Turing machine?

5 votes

How do web browsers find out the MAC address?

5 votes
Accepted

Basic Theta-notation question

5 votes
Accepted

Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems

5 votes

Sequence to explore the complexity of the NP problem

5 votes
Accepted

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

5 votes

Isomorphisms between regular graphs of same degree

5 votes

I think you can always compress compressed data, is it true?

5 votes

Give a Context Free Language, is the complement of this language always recursive(REC)?

4 votes
Accepted

Two's complement general formula

4 votes
Accepted

Calculating the number of assignments satisfying a general propositional formula

4 votes

Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?

4 votes
Accepted

Why does $L\subseteq \textbf{P} \cap \textbf{NP}$ is $\textbf{NP}$-complete imply $\textbf{NP} = \textbf{P}$?

4 votes
Accepted

What should I call algorithms with non-linear non-constant time?

4 votes

When are invariants true inside of a loop?

4 votes
Accepted

Showing that $BPP \subseteq EXP$?

3 votes
Accepted

An example of a computable problem that is not in P

3 votes

Is the P vs NP problem, an NP or co-NP problem?

3 votes
Accepted

Prove that there is no computability reduction HP $\le$ $\Sigma$*

3 votes
Accepted

Why is EXPTIME in EXPSPACE?

3 votes
Accepted

The power of relativised proofs

1
2 3 4 5