User Iddo Tzameret

42 votes

Major unsolved problems in theoretical computer science?

answered Aug 19, 2010 at 21:55

25 votes

Does $VP \neq VNP$ imply $P \neq NP$?

answered Dec 22, 2010 at 15:42

22 votes

Accepted

Well known classes of boolean formulas that require exponentially long resolution proofs

answered Aug 20, 2010 at 11:57

22 votes

Using lambda calculus to derive time complexity?

answered Aug 21, 2010 at 22:48

21 votes

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

answered Oct 5, 2010 at 10:25

14 votes

Formal representation of rings in computations

answered Oct 21, 2010 at 7:30

13 votes

Start learning proof complexity

answered Oct 10, 2013 at 10:54

12 votes

Accepted

$\mathsf{NC^1}$ circuit evaluation

answered Oct 22, 2013 at 6:43

12 votes

Conditions for tractability of 3SAT-Satisfiability

answered Nov 19, 2010 at 7:53

10 votes

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

answered Oct 11, 2014 at 14:39

10 votes

Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence

answered Oct 30, 2012 at 12:15

10 votes

Evaluating symmetric polynomials

answered Dec 22, 2015 at 17:14

8 votes

Lower bounds for noncommutative arithmetic circuits with exact division?

answered Jan 24, 2016 at 1:16

7 votes

Graph theoretic restriction to Proofs in Proof Complexity Theory

answered Dec 21, 2015 at 21:22

1 vote

Resolution vs Nondeterministic Search Problems

answered Apr 5, 2018 at 10:15

Stack Exchange Network

15 Answers

Major unsolved problems in theoretical computer science?

Does $VP \neq VNP$ imply $P \neq NP$?

Well known classes of boolean formulas that require exponentially long resolution proofs

Using lambda calculus to derive time complexity?

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Formal representation of rings in computations

Start learning proof complexity

$\mathsf{NC^1}$ circuit evaluation

Conditions for tractability of 3SAT-Satisfiability

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence

Evaluating symmetric polynomials

Lower bounds for noncommutative arithmetic circuits with exact division?

Graph theoretic restriction to Proofs in Proof Complexity Theory

Resolution vs Nondeterministic Search Problems