rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 6 years, 11 months
  • Last seen this week
5 votes
0 answers
160 views

Can minimal CNF contain clause longer than initial CNF?

4 votes
2 answers
268 views

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

3 votes
1 answer
197 views

Solving 2-CNF TQBF with #SAT solver?

3 votes
2 answers
345 views

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

3 votes
1 answer
362 views

Satisfiabililty sufficient condition?

3 votes
1 answer
124 views

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

3 votes
1 answer
213 views

Is boolean formula isomorphism NP-complete?

3 votes
1 answer
440 views

Linear time multiplication on RAM machine?

3 votes
0 answers
46 views

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

3 votes
0 answers
57 views

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

3 votes
1 answer
31 views

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

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?

2 votes
1 answer
139 views

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

2 votes
2 answers
163 views

Exponential Time Hypothesis and the input size vs number of variables

2 votes
0 answers
17 views

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

2 votes
2 answers
117 views

Do we know something about this refutation method for SAT?

2 votes
1 answer
531 views

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

2 votes
1 answer
195 views

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

2 votes
1 answer
557 views

Is this case of weighted 2SAT NP-complete?

2 votes
1 answer
53 views

2CNF with 3 variable occurences

2 votes
3 answers
5k views

3-SAT with 3 variable occurences

2 votes
1 answer
167 views

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

2 votes
1 answer
2k views

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

1 vote
2 answers
2k views

Why AKS primality test is called polynomial?

1 vote
0 answers
86 views

Question about $\mathsf{Almost–PSPACE}$

1 vote
1 answer
214 views

How can I understand if reduction is Karp reduction?

1 vote
1 answer
77 views

Correctness of following algorithm for 3-QCNF?

1 vote
1 answer
258 views

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

1 vote
1 answer
105 views

How 2-QCNF algorithm works?

1 vote
1 answer
64 views

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