User Michael Wehar

24 votes

1 answer

960 views

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

asked Jan 12, 2015 at 19:10

19 votes

2 answers

2k views

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

time-complexity sat turing-machines np nondeterminism

asked Oct 22, 2015 at 8:47

18 votes

0 answers

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

ds.algorithms matrices computational-geometry search-problem boolean-matrix

asked Sep 18, 2020 at 18:04

17 votes

1 answer

739 views

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

cc.complexity-theory oracles relativization pspace structural-complexity

asked Apr 9, 2017 at 6:23

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?

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

asked Nov 6, 2015 at 3:37

14 votes

0 answers

656 views

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

np-hardness sat matrices clique fine-grained

asked Nov 5, 2015 at 17:23

14 votes

1 answer

853 views

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

cc.complexity-theory time-complexity lower-bounds turing-machines machine-models

asked Nov 8, 2020 at 20:41

14 votes

0 answers

465 views

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

cc.complexity-theory complexity-classes reductions succinct

asked Jan 10, 2019 at 6:34

14 votes

1 answer

335 views

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

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

asked Jan 16, 2018 at 7:50

13 votes

4 answers

1k views

Finding the sparsest solution to a system of linear equations

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

asked Dec 16, 2015 at 7:19

11 votes

1 answer

300 views

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

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

asked Jan 20, 2018 at 17:50

10 votes

1 answer

217 views

On sparse complete sets and P vs L

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

asked Jan 18, 2018 at 8:39

10 votes

1 answer

331 views

What is the state complexity of the copy language?

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

asked Jul 23, 2015 at 4:31

10 votes

1 answer

854 views

Complexity of k-clique for hypergraphs

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

asked Aug 9, 2015 at 14:25

9 votes

1 answer

252 views

Consequences of a distillation algorithm for PSPACE

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

asked Nov 19, 2016 at 0:59

9 votes

0 answers

153 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

asked Mar 10, 2017 at 3:35

9 votes

0 answers

649 views

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

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

asked Mar 29, 2017 at 14:30

9 votes

0 answers

683 views

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

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

asked Jan 14, 2018 at 18:17

9 votes

1 answer

215 views

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

cc.complexity-theory ds.algorithms graph-algorithms time-complexity nondeterminism

asked Feb 16, 2021 at 11:20

8 votes

3 answers

755 views

Non-Orthogonal Vectors Problem

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

asked Sep 17, 2018 at 0:05

8 votes

0 answers

283 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

asked Apr 1, 2017 at 17:13

8 votes

1 answer

365 views

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

cc.complexity-theory complexity-classes oracles relativization pspace

asked Apr 27, 2017 at 15:14

8 votes

1 answer

447 views

Are there more polynomial time problems with complexity lower bounds?

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

asked Nov 12, 2015 at 16:31

7 votes

1 answer

959 views

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

np-hardness sat reductions clique fine-grained

asked Mar 19, 2016 at 15:07

6 votes

1 answer

517 views

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

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

asked Jun 30, 2018 at 0:13

5 votes

0 answers

143 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

asked Jun 15, 2018 at 17:15

5 votes

1 answer

1k views

What is the complexity of counting parse trees?

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

asked Jan 19, 2018 at 4:14

5 votes

2 answers

349 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

asked Feb 5, 2020 at 4:24

5 votes

0 answers

929 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

asked Apr 8, 2015 at 22:15

4 votes

1 answer

462 views

Can we efficiently convert from NFA to smallest equivalent DFA?

cc.complexity-theory ds.algorithms fl.formal-languages automata-theory minimization

asked Mar 22, 2021 at 21:37

Stack Exchange Network

current community

your communities

more stack exchange communities

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?

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

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?

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

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)))$?

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

Non-Orthogonal Vectors Problem

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

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

Are there more polynomial time problems with complexity lower bounds?

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

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?

What is the complexity of counting parse trees?

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

Can we efficiently convert from NFA to smallest equivalent DFA?