# All Questions

12,815 questions
Filter by
Sorted by
Tagged with
63 views

1 vote
47 views

### Short learned clauses for XSAT

Are there any studies about how effective a limited resolution pre-processor is for DPLL-CDCL type SAT solvers? By limited resolution pre-processor I mean a pre-processor that generates short (1,2, or ...
57 views

### Undecidability of games with limited hidden state

Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable. Question:...
• 2,577
70 views

### Complexity of an algorithm involving permutations

I'm looking to figure out the computational complexity of an algorithm in an application I've written. The application computes the answer to a problem that is $\#P$-hard, and the algorithm I'm asking ...
• 111
1 vote
26 views

### How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

Thanks for reading, let me provide the definitions first. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they ...
• 11
68 views

### On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
83 views

### Working out the constants and probabilities of Stockmeyer's approximate counting algorithm

Stockmeyer's 1983 result on approximate counting using a randomness states that if we have some SAT instance $x$ with $C(x)$ satisfying assignments, then we can find the minimum set of $m$ hash ...
• 171
180 views

### Calculation on Sparsification and critical clauses in SAT

I followed from this question. I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$ But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$. ...
• 127
287 views

### Is sorting NP-complete?

SORTING problem. Input: A poset which corresponds to a partially sorted list of different numbers. Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array. ...
• 13.8k
52 views

### What is the complexity class of this problem?

What is the complexity class of finding $\# SAT\bmod q$ when $q$ is a prime or prime power and $-\log q\leq \# SAT\bmod q\leq\log q$ holds? Is it $FewP$?
• 12.8k
188 views

### Is Optimal Swap Sorting NP-Hard?

Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...