User Michael Wehar

25 votes

1 answer

1k views

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

asked Jan 12, 2015 at 19:10

20 votes

2 answers

2k views

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

asked Oct 22, 2015 at 8:47

18 votes

1 answer

887 views

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

asked Apr 9, 2017 at 6:23

18 votes

0 answers

474 views

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

asked Sep 18, 2020 at 18:04

15 votes

2 answers

1k views

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

asked Nov 6, 2015 at 3:37

14 votes

0 answers

699 views

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

asked Nov 5, 2015 at 17:23

14 votes

1 answer

1k views

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

asked Nov 8, 2020 at 20:41

14 votes

0 answers

475 views

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

asked Jan 10, 2019 at 6:34

14 votes

1 answer

393 views

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

asked Jan 16, 2018 at 7:50

13 votes

4 answers

1k views

Finding the sparsest solution to a system of linear equations

asked Dec 16, 2015 at 7:19

11 votes

1 answer

335 views

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

asked Jan 20, 2018 at 17:50

10 votes

1 answer

242 views

On sparse complete sets and P vs L

asked Jan 18, 2018 at 8:39

10 votes

1 answer

352 views

What is the state complexity of the copy language?

asked Jul 23, 2015 at 4:31

10 votes

1 answer

994 views

Complexity of k-clique for hypergraphs

asked Aug 9, 2015 at 14:25

9 votes

1 answer

513 views

Are there more polynomial time problems with complexity lower bounds?

asked Nov 12, 2015 at 16:31

9 votes

1 answer

537 views

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

asked Apr 27, 2017 at 15:14

9 votes

1 answer

266 views

Consequences of a distillation algorithm for PSPACE

asked Nov 19, 2016 at 0:59

9 votes

0 answers

171 views

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

asked Mar 10, 2017 at 3:35

9 votes

0 answers

1k views

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

asked Mar 29, 2017 at 14:30

9 votes

1 answer

904 views

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

asked Jan 14, 2018 at 18:17

9 votes

3 answers

959 views

Non-Orthogonal Vectors Problem

asked Sep 17, 2018 at 0:05

9 votes

1 answer

230 views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

asked Feb 16, 2021 at 11:20

8 votes

0 answers

301 views

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

asked Apr 1, 2017 at 17:13

7 votes

1 answer

1k views

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

asked Mar 19, 2016 at 15:07

7 votes

1 answer

223 views

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

asked Jan 13, 2019 at 20:28

7 votes

1 answer

2k views

What is the complexity of counting parse trees?

asked Jan 19, 2018 at 4:14

6 votes

1 answer

884 views

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

asked Jun 30, 2018 at 0:13

5 votes

0 answers

148 views

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

asked Jun 15, 2018 at 17:15

5 votes

2 answers

446 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?

asked Feb 5, 2020 at 4:24

5 votes

0 answers

1k views

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

asked Apr 8, 2015 at 22:15

Stack Exchange Network

33 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?

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

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

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

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

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

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

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

Are there more polynomial time problems with complexity lower bounds?

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

Consequences of a distillation algorithm for PSPACE

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

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

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

Non-Orthogonal Vectors Problem

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

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

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

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

What is the complexity of counting parse trees?

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

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

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?

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