user avatar
user avatar
user avatar
Michael Wehar
  • Member for 9 years, 5 months
  • Last seen more than a month ago
24 votes
1 answer
960 views

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

19 votes
2 answers
2k views

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

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?

17 votes
1 answer
739 views

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

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?

14 votes
0 answers
656 views

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

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?

14 votes
0 answers
465 views

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

14 votes
1 answer
335 views

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

13 votes
4 answers
1k views

Finding the sparsest solution to a system of linear equations

11 votes
1 answer
300 views

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

10 votes
1 answer
217 views

On sparse complete sets and P vs L

10 votes
1 answer
331 views

What is the state complexity of the copy language?

10 votes
1 answer
854 views

Complexity of k-clique for hypergraphs

9 votes
1 answer
252 views

Consequences of a distillation algorithm for PSPACE

9 votes
0 answers
153 views

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

9 votes
0 answers
649 views

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

9 votes
0 answers
683 views

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

9 votes
1 answer
215 views

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

8 votes
3 answers
755 views

Non-Orthogonal Vectors Problem

8 votes
0 answers
283 views

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

8 votes
1 answer
365 views

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

8 votes
1 answer
447 views

Are there more polynomial time problems with complexity lower bounds?

7 votes
1 answer
959 views

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

6 votes
1 answer
517 views

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

5 votes
0 answers
143 views

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

5 votes
1 answer
1k views

What is the complexity of counting parse trees?

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?

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

4 votes
1 answer
462 views

Can we efficiently convert from NFA to smallest equivalent DFA?