User rus9384

4 votes

2 answers

256 views

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

asked May 27, 2017 at 9:36

4 votes

0 answers

122 views

Can minimal CNF contain clause longer than initial CNF?

asked Jun 17, 2017 at 12:57

3 votes

1 answer

356 views

Satisfiabililty sufficient condition?

asked Jul 11, 2017 at 23:54

3 votes

1 answer

117 views

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

asked Aug 9, 2017 at 13:15

3 votes

1 answer

186 views

Solving 2-CNF TQBF with #SAT solver?

asked Jun 2, 2017 at 9:15

3 votes

2 answers

340 views

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

asked Jun 8, 2017 at 10:07

3 votes

1 answer

198 views

Is boolean formula isomorphism NP-complete?

asked Aug 28, 2017 at 1:49

3 votes

1 answer

422 views

Linear time multiplication on RAM machine?

asked Sep 9, 2017 at 0:27

3 votes

0 answers

44 views

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

asked Feb 14, 2018 at 7:39

3 votes

0 answers

56 views

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

asked Nov 17, 2020 at 17:06

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

123 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

2 answers

155 views

Exponential Time Hypothesis and the input size vs number of variables

asked May 13, 2022 at 12:44

2 votes

2 answers

113 views

Do we know something about this refutation method for SAT?

asked Sep 13, 2017 at 22:33

2 votes

1 answer

520 views

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

asked Jun 13, 2017 at 2:23

2 votes

1 answer

175 views

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

asked Aug 12, 2017 at 11:23

2 votes

1 answer

511 views

Is this case of weighted 2SAT NP-complete?

asked Aug 19, 2017 at 16:08

2 votes

1 answer

51 views

2CNF with 3 variable occurences

asked Sep 1, 2017 at 6:27

2 votes

3 answers

5k views

3-SAT with 3 variable occurences

asked Sep 5, 2017 at 8:22

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

162 views

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

asked Jun 24, 2017 at 13:54

1 vote

1 answer

202 views

How can I understand if reduction is Karp reduction?

asked Jun 29, 2017 at 10:07

1 vote

1 answer

77 views

Correctness of following algorithm for 3-QCNF?

asked Jun 21, 2017 at 0:54

1 vote

1 answer

255 views

Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

asked Aug 11, 2017 at 14:49

1 vote

1 answer

104 views

How 2-QCNF algorithm works?

asked Aug 7, 2017 at 11:25

1 vote

2 answers

2k views

Why AKS primality test is called polynomial?

asked May 18, 2017 at 14:08

1 vote

0 answers

85 views

Question about $\mathsf{Almost–PSPACE}$

asked Jun 5, 2017 at 8:41

1 vote

1 answer

62 views

If we allow a database, what complexity class it is?

asked Sep 6, 2017 at 0:54

1 vote

0 answers

64 views

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

asked Aug 24, 2017 at 9:21

1 vote

0 answers

142 views

Correct implication for 3SAT from this theorem?

asked Aug 13, 2017 at 12:09

Stack Exchange Network

53 Questions

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

Can minimal CNF contain clause longer than initial CNF?

Satisfiabililty sufficient condition?

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

Solving 2-CNF TQBF with #SAT solver?

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

Is boolean formula isomorphism NP-complete?

Linear time multiplication on RAM machine?

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?

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

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

Exponential Time Hypothesis and the input size vs number of variables

Do we know something about this refutation method for SAT?

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

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

Is this case of weighted 2SAT NP-complete?

2CNF with 3 variable occurences

3-SAT with 3 variable occurences

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

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

How can I understand if reduction is Karp reduction?

Correctness of following algorithm for 3-QCNF?

Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

How 2-QCNF algorithm works?

Why AKS primality test is called polynomial?

Question about $\mathsf{Almost–PSPACE}$

If we allow a database, what complexity class it is?

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

Correct implication for 3SAT from this theorem?