As of May 31, 2023, we have updated our Code of Conduct.
Kaveh's user avatar
Kaveh's user avatar
Kaveh's user avatar
Kaveh
  • Member for 11 years, 3 months
  • Last seen more than a week ago
454 votes
Accepted

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

227 votes

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

71 votes
Accepted

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

60 votes

How not to solve P=NP?

47 votes
Accepted

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

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

23 votes

Why is quicksort better than other sorting algorithms in practice?

23 votes

Why is Relativization a barrier?

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 to prove that a language is not context-free?

18 votes

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

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

Turing machine - infinite tape - does that thing exist?

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?

14 votes
Accepted

Is Karp Reduction identical to Levin Reduction

13 votes
Accepted

Decision problem such that any algorithm admits an exponentially faster algorithm

12 votes
Accepted

Turing complete and computational power

12 votes

Concrete understanding of difference between PP and BPP definitions

12 votes

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

12 votes

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

11 votes
Accepted

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

11 votes

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

11 votes

P-Completeness and Parallel Computation

11 votes

What is required for universal analogue computation?

11 votes
Accepted

Why is this example a regular language?

1
2 3 4 5 6