Kaveh's user avatar
Kaveh's user avatar
Kaveh's user avatar
Kaveh
  • Member for 13 years, 8 months
  • Last seen this week
16 votes
Accepted

Non-constructive proofs vs. efficient algorithms

15 votes
Accepted

Busy Beaver modulo 2

12 votes

Interpretation of the Second Incompleteness Theorem

11 votes
Accepted

Descriptive complexity theoretic-characterizations of P and NP

11 votes

Where to publish a paper on the Mafia game?

10 votes

How would calculus be possible in a finitist axiom system?

10 votes

Mathematics of privacy?

9 votes

Computable nonstandard models for weak systems of arithemtic

8 votes
Accepted

Structure theorems for Turing-decidable languages?

7 votes
Accepted

The best text to study both incompleteness theorems

7 votes

Is there a general setting for self-reference?

7 votes

Don't the axioms of set theory implicitly assume numbers?

7 votes

Solving NP problems in (usually) Polynomial time?

7 votes
Accepted

Oracle Results: P^A = NP^A

6 votes

Is the Axiom of Union independent of the rest of ZF?

6 votes

Proof systems and their hierarchy

6 votes

Are computable models sufficient?

5 votes

Definition of relativization of complexity class

5 votes
Accepted

$\mu$-recursive definitions for the complexity classes P, NP, etc

4 votes

Propositions equivalent to the completeness of the real numbers

4 votes

Lower Bounds in Theoretical Computer Science

4 votes

What is the time complexity of computing sin(x) to t bits of precision?

4 votes

What was Gödel's real achievement?

3 votes

Most 'obvious' open problems in complexity theory

3 votes

Difference between turnstile and implication

3 votes

Why can Diophantine equations represent exponential growth?

3 votes

A programming language that can only create algorithms with polynomial runtime?

3 votes

Ordinals and complexity classes

3 votes

Formal verification in complexity theory

3 votes

Is there a notion of Skolemization for continuous logic?