Theoretical Computer Science
Jan Johannsen
Meta user
Network profile
Summary Answers Questions Tags Badges Favorites Bounties Reputation All actions

40 Answers

Newest Activity Votes
21
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
17
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
Mar 1 '17 at 8:40
16
$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$
Oct 14 '11 at 16:47
15
Theoretical explanations for practical success of SAT solvers?
Mar 31 '17 at 14:20
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
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
May 17 '13 at 9:06
14
Statements that imply $\mathbf{P}\neq \mathbf{NP}$
Oct 10 '14 at 11:24
12
When have we found better bounds for known algorithms?
Aug 14 '19 at 12:18
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
10
What is the best known FPT result for 3-hitting set?
May 30 '16 at 8:03
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
How often is the ECCC queue cleared?
Nov 13 '17 at 8:31
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
Reductions in Descriptive Complexity
May 31 '19 at 8:20
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
Sequent calculus for nonmonotonic/defeasible logics?
Oct 24 '16 at 13:33
1 2