Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

  7. current community

    your communities

    more stack exchange communities

    company blog
Theoretical Computer Science
Jan Johannsen
Meta User
Network Profile
summary answers questions tags badges favorites bounties reputation all actions

38 Answers

newest activity votes
20
Minimum True Monotone 3SAT
Nov 23 '11 at 16:17
19
Has there been any research on $k$-SAT above the satisfiability threshold?
Apr 9 '14 at 15:08
18
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
Mar 1 '17 at 8:40
16
Theoretical explanations for practical success of SAT solvers?
Mar 31 '17 at 14:20
16
$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$
Oct 14 '11 at 16:47
15
What is an equivalent definition of mP/poly in terms of a Turing machine?
Jun 18 '15 at 12:37
15
What are the compelling reasons for believing $L\neq P$?
Oct 9 '13 at 8:05
15
Golden ratio or Pi in the running time
Jan 8 '13 at 8:47
14
Statements that imply $\mathbf{P}\neq \mathbf{NP}$
Oct 10 '14 at 11:24
13
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
May 17 '13 at 9:06
11
What is the best known FPT result for 3-hitting set?
May 30 '16 at 8:03
11
Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?
Jan 31 '13 at 8:51
10
Why is the circuit class AC0 unavoidable?
Mar 20 '18 at 9:23
9
How often is the ECCC queue cleared?
Nov 13 '17 at 8:31
9
Are there any propositional proof systems which are not Cook-Reckhow proof systems?
Dec 9 '15 at 9:16
9
Do Higher-Order Functions provide more power to Functional Programming?
Jun 5 '12 at 17:39
8
Graph theoretic restriction to Proofs in Proof Complexity Theory
Dec 18 '15 at 10:05
8
Simply-stated restriction on imperative programming language that captures the elementary functions?
Dec 7 '12 at 9:36
8
Set of functions computable in polynomial time
Nov 13 '12 at 13:56
8
Ruzzo-Simon-Tompa oracle access mechanism
Jun 13 '12 at 15:00
8
Well known classes of boolean formulas that require exponentially long resolution proofs
Jan 20 '12 at 12:42
8
Well known classes of boolean formulas that require exponentially long resolution proofs
Nov 18 '11 at 9:48
7
Boolean circuits which correspond to L/poly
Oct 5 '18 at 8:54
7
variations of SAT
Sep 9 '13 at 8:00
7
Theories which characterize classes of computational complexity
Nov 18 '11 at 14:55
6
Sequent calculus for nonmonotonic/defeasible logics?
Oct 24 '16 at 13:33
6
What are the simplest turing-complete systems?
Jul 3 '13 at 11:22
5
NP-Complete Static Square Puzzles
Oct 19 '18 at 7:42
5
Which subproblems of 3SAT are still NP complete?
Apr 16 '15 at 13:52
5
Most memorable CS paper titles
Oct 28 '14 at 15:31
1 2