Kyle Jones
• Member for 9 years, 10 months
• Last seen this week
• Seattle, WA

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 ...

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 ...

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-...

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 ...

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 ...

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 ...

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, ...

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:...

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 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 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 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 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 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 > ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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. ...