Kyle Jones
  • Member for 9 years, 10 months
  • Last seen this week
  • Seattle, WA
Is there a difference between top-down and bottom-up dynamic programming?
31 votes

To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space. If you know what the lowest level ...

View answer
Is finding a solution of a satisfiability problem harder than deciding satisfiability?
Accepted answer
19 votes

As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment. This is because Boolean ...

View answer
Is UTF-8 the final character encoding for all future time?
19 votes

When it comes to software, the future always means needing to handle more data--- bigger files, and more of them in a shorter period of time. How does UTF-8 processing scale in those situations? UTF-...

View answer
NP-complete problems not "obviously" in NP
Accepted answer
19 votes

There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness. [AN6] NON-DIVISIBILITY OF A ...

View answer
What is wrong with this simple proof of P=NP?
15 votes

The monotone version of X3SAT that your proof is based on has the nice property that setting a literal false in one clause will never cause the negation of that literal to be true in another, which ...

View answer
Converting (math) problems to SAT instances
15 votes

Unless you're translating mathematical problems to SAT instances as a learning exercise, your time will be much more fruitfully spent learning about satisfiability modulo theories. SMT will allow you ...

View answer
Is the following problem NP-hard? (or have you seen it before?)
14 votes

What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, ...

View answer
Encoding 1-out-of-n constraint for SAT solvers
14 votes

For the special case of k out of n variables true where k = 1, there is commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects by Klieber and Kwon. Simplified:...

View answer
Is 2-SAT with XOR-relations NP-complete?
Accepted answer
13 votes

2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT. Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $...

View answer
Is the "subset product" problem NP-complete?
Accepted answer
13 votes

A comment mentions a reduction from X3C to SUBSET PRODUCT attributed to Yao. Given the target of the reduction it wasn't hard to guess what the reduction was likely to have been. Definitions: EXACT ...

View answer
Can there be a perfect chess algorithm?
Accepted answer
13 votes

Your question is akin to the old chestnut: "What happens when an irresistible force meets an immovable object?" The problem is in the question itself: the two entities as described cannot exist in ...

View answer
What is wrong with this seeming contradiction with a paper about AND-compression of SAT?
Accepted answer
12 votes

The confusion arises from a misunderstanding of what being polynomial in the size of the largest instance means. It does not mean that polynomial growth of the compressor's output is allowed as the ...

View answer
Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?
11 votes

The deterministic time hierarchy theorem precludes all problems in P being decided in linear time. If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll ...

View answer
How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?
11 votes

The largest 12 digit number in base 10 is $10^{12} - 1$. In general the largest $n$ position number in a base $b$ is $b^{n} - 1$. So in your case you need a base large enough that $b^{9} - 1 > ...

View answer
Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"?
Accepted answer
11 votes

A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign. So the only time that a SAT solver would save by early notification is the time it ...

View answer
If one shows that UNIQUE k-SAT is in P, does it imply P=NP?
Accepted answer
11 votes

This is still an open question; UP is not known to be equivalent to NP. In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under ...

View answer
Recipe book for SAT encodings?
Accepted answer
10 votes

I read a survey paper a few years ago that seems relevant, "Successful SAT Encoding Techniques" by Magnus Björk. Abstract: This article identifies good practices for SAT encodings by ...

View answer
Should activation function be monotonic in neural networks?
Accepted answer
10 votes

During the training phase, backpropagation informs each neuron how much it should influence each neuron in the next layer. If the activation function isn't monotonic then increasing the neuron's ...

View answer
Random restarts for unsatisfiable instances
Accepted answer
9 votes

There is some research in this area. In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both ...

View answer
Why is the class NP-Complete important compared to NP-hard?
9 votes

From the point of view of someone who writes code for a living, having a good familiarity with NP-completeness is important for: 1. Recognizing when you're barking up the wrong tree NP-complete ...

View answer
Is order of bits in byte really not of concern?
Accepted answer
9 votes

Bytes are transferred from memory to disk using an I/O protocol (e.g. SCSI) that specifies the bit order of transmission in the case of a serial protocol, or for parallel protocols specifies which pin ...

View answer
Supporting data structures for SAT local search
Accepted answer
9 votes

The needed data structure is an occur list, a list for each variable containing the clauses the variable occurs in. These lists are built once, when the CNF is first read. They are used in steps 3 ...

View answer
Would it be possible to use the cloud for RAM?
Accepted answer
8 votes

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work. However, today's ...

View answer
Why is pure literal elimination absent in DPLL-based algorithms like Chaff?
Accepted answer
7 votes

Solvers that use the two-watched-literals algorithm to implement unit propagation don't keep track of which clauses have been deleted (by implication) to produce the subformula implied by the current ...

View answer
I am having trouble understanding (and implementing) logistic regression for classifying into three classes
Accepted answer
7 votes

How do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two). If you have $n$ possible classes then you must train $n$ logistic classifiers on your ...

View answer
Could an NP-hard problem have a mechanical or physical solution method?
Accepted answer
7 votes

Scott Aaronson examines "mechanical" solutions to NP-complete problems in the odd and entertaining paper "NP-complete Problems and Physical Reality". The paper is mostly theoretical discussions of ...

View answer
Conflict Driven Clause Learning backtracking clarification
Accepted answer
7 votes

Here's the relevant paragraph from the MiniSAT paper: The decision phase will continue until either all variables have been assigned, in which case we have a model, or a conflict has occurred. On ...

View answer
Why is DPLL better than brute force?
Accepted answer
7 votes

Local (stochastic) search is all about clever navigation of the search space. DPLL's advantage is pruning the search space of large swaths of assignments that provably cannot satisfy the formula. ...

View answer
Solving SAT using tableau calculus
Accepted answer
7 votes

It can be, but the solution process is equivalent to converting a CNF formula to DNF, which is NP-hard. You will at worst end up exploring an exponential number of disjunction branches.

View answer
Are there more easy SAT Problems?
7 votes

(1) is hard to answer unless you clarify what you mean by "versions of SAT problem." If we limit ourselves to the classes listed in Schaefer's "The Complexity of Satisfiability Problems", the only ...

View answer
1
2 3 4 5 6