User dkaeae

22 votes

Accepted

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

answered Jan 30, 2019 at 16:40

12 votes

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

computability proof-techniques decision-problem uncountability

answered Jul 1, 2019 at 12:57

11 votes

Accepted

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

complexity-theory np-complete np-hard satisfiability

answered Apr 17, 2019 at 8:06

10 votes

Accepted

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

cryptography security

answered Feb 23, 2019 at 11:39

9 votes

Accepted

How are problems classified in Complexity Theory?

complexity-theory

answered Mar 29, 2019 at 9:56

8 votes

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

terminology asymptotics big-o-notation

answered May 15, 2019 at 8:27

7 votes

Intuition behind eigenvalues of an adjacency matrix

graphs adjacency-matrix

answered May 28, 2019 at 14:03

5 votes

Sequence to explore the complexity of the NP problem

np-hard np

answered May 27, 2019 at 7:50

5 votes

Accepted

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

complexity-theory logic counting propositional-logic

answered Jul 15, 2019 at 14:11

5 votes

Accepted

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

turing-machines reference-request nondeterminism

answered Aug 8, 2019 at 8:42

5 votes

Accepted

Halting problem in EXP-complete

complexity-theory reductions

answered Aug 12, 2019 at 8:17

5 votes

How do web browsers find out the MAC address?

computer-networks routing ip

answered Aug 22, 2019 at 15:06

5 votes

Accepted

Basic Theta-notation question

asymptotics

answered Aug 23, 2019 at 8:13

5 votes

Accepted

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

complexity-theory turing-machines computability space-complexity

answered Mar 1, 2019 at 15:35

5 votes

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

information-theory data-compression

answered Nov 23, 2018 at 7:25

5 votes

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

turing-machines context-free

answered Jan 10, 2019 at 17:16

4 votes

Accepted

Two's complement general formula

binary numeral-representations

answered Dec 6, 2018 at 10:53

4 votes

Isomorphisms between regular graphs of same degree

graphs graph-isomorphism

answered Mar 6, 2019 at 12:48

4 votes

Accepted

Calculating the number of assignments satisfying a general propositional formula

time-complexity satisfiability polynomial-time

answered Feb 20, 2019 at 12:06

4 votes

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

complexity-theory time-complexity

answered Feb 21, 2019 at 9:05

4 votes

Accepted

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

complexity-theory

answered Jan 24, 2019 at 9:56

4 votes

Accepted

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

complexity-theory time-complexity terminology runtime-analysis big-o-notation

answered May 7, 2019 at 6:58

3 votes

Accepted

Complexity class for NP with access to a DP oracle

complexity-theory oracle-machines

answered May 6, 2019 at 13:33

3 votes

Accepted

The power of relativised proofs

oracle-machines relativization

answered May 8, 2019 at 16:35

3 votes

Accepted

What is the specific name for basic data types?

terminology abstract-data-types

answered May 23, 2019 at 11:33

3 votes

Accepted

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

predicate-logic

answered May 24, 2019 at 7:15

3 votes

Accepted

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

one-way-functions

answered Jun 17, 2019 at 7:13

3 votes

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

computer-networks communication-protocols ip

answered Jun 4, 2019 at 7:17

3 votes

When are invariants true inside of a loop?

loop-invariants

answered Aug 28, 2019 at 15:37

3 votes

Accepted

An example of a computable problem that is not in P

complexity-theory computability np

answered Aug 22, 2019 at 7:24

Stack Exchange Network

current community

your communities

more stack exchange communities

142 Answers

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

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

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

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

How are problems classified in Complexity Theory?

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

Intuition behind eigenvalues of an adjacency matrix

Sequence to explore the complexity of the NP problem

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

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

Halting problem in EXP-complete

How do web browsers find out the MAC address?

Basic Theta-notation question

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

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

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

Two's complement general formula

Isomorphisms between regular graphs of same degree

Calculating the number of assignments satisfying a general propositional formula

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

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

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

Complexity class for NP with access to a DP oracle

The power of relativised proofs

What is the specific name for basic data types?

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

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

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

When are invariants true inside of a loop?

An example of a computable problem that is not in P