User rus9384

5 votes

0 answers

166 views

Can minimal CNF contain clause longer than initial CNF?

asked Jun 17, 2017 at 12:57

4 votes

2 answers

274 views

Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

asked May 27, 2017 at 9:36

4 votes

1 answer

218 views

Is boolean formula isomorphism NP-complete?

asked Aug 28, 2017 at 1:49

3 votes

1 answer

453 views

Linear time multiplication on RAM machine?

asked Sep 9, 2017 at 0:27

3 votes

3 answers

6k views

3-SAT with 3 variable occurences

asked Sep 5, 2017 at 8:22

3 votes

1 answer

201 views

Solving 2-CNF TQBF with #SAT solver?

asked Jun 2, 2017 at 9:15

3 votes

2 answers

350 views

Is it possible to prove $\mathsf{BPP = NP}$ statistically?

asked Jun 8, 2017 at 10:07

3 votes

1 answer

371 views

Satisfiabililty sufficient condition?

asked Jul 11, 2017 at 23:54

3 votes

1 answer

126 views

What is complexity class for #XOR-2-SAT?

asked Aug 9, 2017 at 13:15

3 votes

0 answers

50 views

How hard is it to find the length of multiplicative 2-partition?

asked Feb 14, 2018 at 7:39

3 votes

0 answers

57 views

Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?

asked Nov 17, 2020 at 17:06

3 votes

1 answer

38 views

Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?

asked Mar 7 at 9:24

2 votes

1 answer

63 views

Number of graphs that almost contain a $k$-clique

asked May 12 at 17:11

2 votes

0 answers

32 views

Complexity of strong graph realization problem

asked Jun 9 at 14:51

2 votes

0 answers

13 views

Are $\#Clique$ and $\#Coloring$ $\#\mathsf P$-hard on perfect graphs?

asked Jul 13 at 16:23

2 votes

2 answers

177 views

Exponential Time Hypothesis and the input size vs number of variables

asked May 13, 2022 at 12:44

2 votes

1 answer

144 views

Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

asked Aug 12, 2020 at 14:43

2 votes

0 answers

18 views

Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?

asked Dec 11, 2023 at 17:48

2 votes

1 answer

176 views

Was it known that $\mathsf{LTIME \subsetneq NLTIME}$?

asked Jun 24, 2017 at 13:54

2 votes

1 answer

2k views

$NP \ vs \ co-NP$: tautology to SAT and vice versa?

asked May 19, 2017 at 15:29

2 votes

1 answer

63 views

Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

asked Dec 7, 2017 at 6:28

2 votes

1 answer

138 views

Is such variant of SAT always satisfiable?

asked Sep 10, 2017 at 22:11

2 votes

2 answers

119 views

Do we know something about this refutation method for SAT?

asked Sep 13, 2017 at 22:33

2 votes

1 answer

542 views

Reduction from 2-SAT to 2-XOR-SAT?

asked Jun 13, 2017 at 2:23

2 votes

1 answer

54 views

2CNF with 3 variable occurences

asked Sep 1, 2017 at 6:27

2 votes

1 answer

200 views

Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

asked Aug 12, 2017 at 11:23

2 votes

1 answer

589 views

Is this case of weighted 2SAT NP-complete?

asked Aug 19, 2017 at 16:08

1 vote

0 answers

72 views

Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

asked Aug 24, 2017 at 9:21

1 vote

0 answers

147 views

Correct implication for 3SAT from this theorem?

asked Aug 13, 2017 at 12:09

1 vote

1 answer

848 views

SAT to knapsack vs. ETH

asked Aug 18, 2017 at 14:55

Stack Exchange Network

73 Questions

Can minimal CNF contain clause longer than initial CNF?

Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

Is boolean formula isomorphism NP-complete?

Linear time multiplication on RAM machine?

3-SAT with 3 variable occurences

Solving 2-CNF TQBF with #SAT solver?

Is it possible to prove $\mathsf{BPP = NP}$ statistically?

Satisfiabililty sufficient condition?

What is complexity class for #XOR-2-SAT?

How hard is it to find the length of multiplicative 2-partition?

Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?

Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?

Number of graphs that almost contain a $k$-clique

Complexity of strong graph realization problem

Are $\#Clique$ and $\#Coloring$ $\#\mathsf P$-hard on perfect graphs?

Exponential Time Hypothesis and the input size vs number of variables

Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?

Was it known that $\mathsf{LTIME \subsetneq NLTIME}$?

$NP \ vs \ co-NP$: tautology to SAT and vice versa?

Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

Is such variant of SAT always satisfiable?

Do we know something about this refutation method for SAT?

Reduction from 2-SAT to 2-XOR-SAT?

2CNF with 3 variable occurences

Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

Is this case of weighted 2SAT NP-complete?

Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

Correct implication for 3SAT from this theorem?

SAT to knapsack vs. ETH