User Michael Wehar

7

24

votes

1

answer

894

views

Finding the smallest DFA that separates two words without using brute force search?

Feb 25 '17 at 22:32 Community♦ 1

4

19

votes

2

answers

1k

views

Is there a non-deterministic linear time algorithm for CNF-SAT?

time-complexity sat turing-machines np nondeterminism

Oct 23 '15 at 9:54 Marzio De Biasi 21.5k

17

votes

1

answer

505

views

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

cc.complexity-theory oracles relativization pspace structural-complexity

Apr 10 '17 at 11:25 Community♦ 1

1

15

votes

2

answers

930

views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

graph-theory graph-algorithms clique polynomial-time fixed-parameter-tractable

Nov 8 '15 at 2:34 Michael Wehar 4,159

1

14

votes

0

answers

454

views

Is there a P-complete language X such that succinct-X is in P?

cc.complexity-theory complexity-classes reductions succinct

Jan 25 '19 at 22:13 Frank Vega 119

1

14

votes

1

answer

284

views

What are the consequences of $P \subseteq L/poly$?

cc.complexity-theory circuit-complexity polynomial-time advice-and-nonuniformity logspace

Jan 18 '18 at 17:17 William Hoza 1,286

5

14

votes

0

answers

592

views

Does solving matrix multiplication in quadratic time imply that SETH is false?

np-hardness sat matrices clique fine-grained

Nov 27 '15 at 15:40 Michael Wehar 4,159

2

13

votes

4

answers

922

views

Finding the sparsest solution to a system of linear equations

np-hardness linear-algebra linear-programming matrices sparse-matrix

Dec 17 '15 at 16:50 argentpepper 2,221

2

11

votes

1

answer

248

views

Does the space hierarchy theorem generalize to non-uniform computation?

cc.complexity-theory space-bounded space-complexity advice-and-nonuniformity hierarchy-theorems

Jan 22 '18 at 17:07 William Hoza 1,286

2

10

votes

1

answer

179

views

On sparse complete sets and P vs L

cc.complexity-theory complexity-classes reductions polynomial-time logspace

Jan 18 '18 at 17:30 William Hoza 1,286

1

10

votes

1

answer

295

views

What is the state complexity of the copy language?

fl.formal-languages automata-theory grammars context-free

Jul 28 '15 at 8:30 Community♦ 1

2

9

votes

1

answer

512

views

Complexity of k-clique for hypergraphs

cc.complexity-theory graph-theory matrices clique fixed-parameter-tractable

Aug 27 '19 at 6:53 a3nm 6,776

9

votes

0

answers

359

views

What are the best known reductions from SAT to CNF-SAT?

cc.complexity-theory np-hardness sat reductions parameterized-complexity

Mar 29 '17 at 18:53 Michael Wehar 4,159

1

9

votes

0

answers

134

views

Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

cc.complexity-theory circuit-complexity parameterized-complexity

Mar 10 '17 at 3:35 Michael Wehar 4,159

1

9

votes

1

answer

238

views

Consequences of a distillation algorithm for PSPACE

cc.complexity-theory np-hardness parameterized-complexity polynomial-hierarchy pspace

Nov 21 '16 at 18:54 Michael Wehar 4,159

5

8

votes

3

answers

507

views

Non-Orthogonal Vectors Problem

cc.complexity-theory ds.algorithms linear-algebra polynomial-time boolean-matrix

Jul 1 '19 at 1:52 Michael Wehar 4,159

8

votes

1

answer

278

views

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

cc.complexity-theory complexity-classes oracles relativization pspace

Apr 30 '17 at 20:26 Markus Bläser 2,698

3

8

votes

0

answers

265

views

Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?

cc.complexity-theory circuit-complexity sat parameterized-complexity fine-grained

Apr 2 '17 at 22:27 Community♦ 1

1

8

votes

1

answer

390

views

Are there more polynomial time problems with complexity lower bounds?

cc.complexity-theory complexity-classes time-complexity lower-bounds polynomial-time

Nov 14 '15 at 9:14 Whosyourjay 453

6

votes

1

answer

314

views

What are the consequences of solving XOR 3-SAT in Logspace?

cc.complexity-theory complexity-classes sat linear-algebra logspace

Jun 30 '18 at 11:04 Gustav Nordh 1,027

6

votes

1

answer

718

views

On reducing the hardness of CNF-SAT to k-Clique

np-hardness sat reductions clique fine-grained

Mar 22 '16 at 21:20 Ryan Williams 25k

1

5

votes

0

answers

140

views

How hard is it to generate a set of relatively prime numbers between two given bounds?

cc.complexity-theory cr.crypto-security lower-bounds nt.number-theory primes

Jun 17 '18 at 19:46 Michael Wehar 4,159

1

5

votes

0

answers

757

views

Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

space-complexity logspace structural-complexity complexity probabilistic-complexity

Apr 9 '15 at 14:51 Michael Wehar 4,159

4

votes

1

answer

570

views

What is the complexity of counting parse trees?

cc.complexity-theory fl.formal-languages counting-complexity grammars context-free

Jan 20 '18 at 16:13 Michael Wehar 4,159

4

votes

1

answer

344

views

Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

cc.complexity-theory fl.formal-languages automata-theory context-free logspace

Jan 20 '18 at 1:21 Michael Wehar 4,159

1

4

votes

0

answers

193

views

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

cc.complexity-theory circuit-complexity lower-bounds np

Jan 8 '18 at 18:03 Michael Wehar 4,159

3

votes

0

answers

111

views

Is Circuit Minimization $P$-hard under logspace reductions?

boolean-functions reductions polynomial-time logspace circuits

Jan 13 '19 at 20:28 Michael Wehar 4,159

3

votes

1

answer

168

views

Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

cc.complexity-theory circuit-complexity parameterized-complexity structural-complexity

Sep 20 '17 at 9:02 Ronald de Haan 276

1

2

votes

1

answer

164

views

Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

cc.complexity-theory circuit-complexity time-complexity lower-bounds structural-complexity

Feb 18 at 22:26 Michael Wehar 4,159

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

29 Questions

Finding the smallest DFA that separates two words without using brute force search?

Is there a non-deterministic linear time algorithm for CNF-SAT?

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

Is there a P-complete language X such that succinct-X is in P?

What are the consequences of $P \subseteq L/poly$?

Does solving matrix multiplication in quadratic time imply that SETH is false?

Finding the sparsest solution to a system of linear equations

Does the space hierarchy theorem generalize to non-uniform computation?

On sparse complete sets and P vs L

What is the state complexity of the copy language?

Complexity of k-clique for hypergraphs

What are the best known reductions from SAT to CNF-SAT?

Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

Consequences of a distillation algorithm for PSPACE

Non-Orthogonal Vectors Problem

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?

Are there more polynomial time problems with complexity lower bounds?

What are the consequences of solving XOR 3-SAT in Logspace?

On reducing the hardness of CNF-SAT to k-Clique

How hard is it to generate a set of relatively prime numbers between two given bounds?

Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

What is the complexity of counting parse trees?

Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

Is Circuit Minimization $P$-hard under logspace reductions?

Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?