user avatar
user avatar
user avatar
dkaeae
  • Member for 5 years, 2 months
  • Last seen more than a month ago
  • Germany
22 votes
Accepted

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

12 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?

7 votes

Intuition behind eigenvalues of an adjacency matrix

5 votes

Sequence to explore the complexity of the NP problem

5 votes
Accepted

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

5 votes
Accepted

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

5 votes
Accepted

Halting problem in EXP-complete

5 votes

How do web browsers find out the MAC address?

5 votes
Accepted

Basic Theta-notation question

5 votes
Accepted

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

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

Isomorphisms between regular graphs of same degree

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?

3 votes
Accepted

Complexity class for NP with access to a DP oracle

3 votes
Accepted

The power of relativised proofs

3 votes
Accepted

What is the specific name for basic data types?

3 votes
Accepted

In predicate logic, is the "environment" only needed when free variables are present?

3 votes
Accepted

Is the sum $f+g$ of two one-way-functions a one-way-function?

3 votes

Basic Question in networking - why max data size of ip datagram 65535 BYTES and not 65535 bits?

3 votes

When are invariants true inside of a loop?

3 votes
Accepted

An example of a computable problem that is not in P

1
2 3 4 5