rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 6 years
  • Last seen more than a week ago
4 votes
2 answers
250 views

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

4 votes
0 answers
119 views

Can minimal CNF contain clause longer than initial CNF?

3 votes
1 answer
348 views

Satisfiabililty sufficient condition?

3 votes
1 answer
111 views

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

3 votes
1 answer
174 views

Solving 2-CNF TQBF with #SAT solver?

3 votes
2 answers
338 views

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

3 votes
1 answer
180 views

Is boolean formula isomorphism NP-complete?

3 votes
1 answer
395 views

Linear time multiplication on RAM machine?

3 votes
0 answers
43 views

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

3 votes
0 answers
52 views

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

2 votes
1 answer
61 views

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

2 votes
1 answer
106 views

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

2 votes
2 answers
139 views

Exponential Time Hypothesis and the input size vs number of variables

2 votes
2 answers
105 views

Do we know something about this refutation method for SAT?

2 votes
1 answer
495 views

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

2 votes
1 answer
166 views

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

2 votes
1 answer
449 views

Is this case of weighted 2SAT NP-complete?

2 votes
1 answer
51 views

2CNF with 3 variable occurences

2 votes
3 answers
4k views

3-SAT with 3 variable occurences

2 votes
1 answer
2k views

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

2 votes
1 answer
158 views

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

1 vote
1 answer
189 views

How can I understand if reduction is Karp reduction?

1 vote
1 answer
76 views

Correctness of following algorithm for 3-QCNF?

1 vote
1 answer
254 views

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

1 vote
1 answer
93 views

How 2-QCNF algorithm works?

1 vote
2 answers
2k views

Why AKS primality test is called polynomial?

1 vote
0 answers
81 views

Question about $\mathsf{Almost–PSPACE}$

1 vote
1 answer
61 views

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

1 vote
0 answers
60 views

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

1 vote
0 answers
139 views

Correct implication for 3SAT from this theorem?