Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
Kaveh's user avatar
Kaveh's user avatar
Kaveh's user avatar
Kaveh
  • Member for 12 years, 2 months
  • Last seen this week
463 votes
Accepted

What is the definition of P, NP, NP-complete and NP-hard?

230 votes

What is the definition of P, NP, NP-complete and NP-hard?

73 votes
Accepted

Are there subexponential-time algorithms for NP-complete problems?

61 votes

How not to solve P=NP?

47 votes
Accepted

Knapsack problem -- NP-complete despite dynamic programming solution?

37 votes
Accepted

Why are there more non-computable functions than computable ones?

28 votes
Accepted

Are there NP problems, not in P and not NP Complete?

25 votes

Why is Relativization a barrier?

24 votes

Why is quicksort better than other sorting algorithms in practice?

21 votes

Is there a "natural" undecidable language?

20 votes

Why are computable functions also called recursive functions?

19 votes

Why, really, is the Halting Problem so important?

19 votes

How does one know which notation of time complexity analysis to use?

19 votes

How to prove that a language is not context-free?

18 votes
Accepted

Sub language is not Turing-recognizable, or could it be?

18 votes
Accepted

If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B

15 votes
Accepted

Is Karp Reduction identical to Levin Reduction

15 votes

Turing machine - infinite tape - does that thing exist?

15 votes

What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?

14 votes
Accepted

What is the time complexity of generating n-th prime number?

14 votes
Accepted

How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?

13 votes
Accepted

Decision problem such that any algorithm admits an exponentially faster algorithm

13 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

12 votes
Accepted

Turing complete and computational power

12 votes

Concrete understanding of difference between PP and BPP definitions

11 votes

Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

11 votes
Accepted

Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

11 votes

P-Completeness and Parallel Computation

11 votes
Accepted

Decidable non-context-sensitive languages

11 votes

What is required for universal analogue computation?

1
2 3 4 5 6