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

Your algorithm doesn't prove NP = co-NP because you're using a Cook reduction to go from DNF-TAUTOLOGIES to CNF-SAT. NP and co-NP aren't separate complexity classes under Cook reductions, they are ...

Modern languages are heavily optimized, so much so that it is hard to predict if minor code changes will make an algorithm run faster. In particular with matrix math, whether the language ...

One example of a tiling problem that was successfully attacked by reducing it to a SAT instance was rectangular grid coloring. In "Extremely Complex 4-Colored Rectangle-Free Grids: Solution of Open ...

The algorithms mentioned are all fixed-parameter tractable in the size of the cycle. This means that if you fix the cycle size $k$, there's a polynomial time algorithm for finding the cycle as the ...

CNF-SAT can be reduced to QUADRUPLE-SAT by adding two new variables, $x_1$ and $x_2$, and adding the following CNF clauses. $(x_1 \lor \lnot x_1)$ $(x_2 \lor \lnot x_2)$ Because $x_1$ and $x_2$ can ...

An interesting lossless compression algorithm for JPEG images was open-sourced this summer by Dropbox. The algorithm is called "Lepton" and achieves compression by "predicting coefficients in JPEG ...

The most improvement with the least effort will come from adding rapid random restarts to your solver. DPLL is known to exhibit heavy-tailed behavior, producing both short and long search times for ...

Your reasoning is correct. Your "sum-of-products" is more commonly known as disjunctive normal form (DNF). It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so ...

If you use the original specification of the DPLL algorithm, in which the unit rule is applied to a fixed point and then the pure literal rule, then only the unit rule is needed to reach a satisfying ...

One example of compiler intrinsic functions is the floating point math functions that are part of the standard C math library. On CPU architectures with on-chip support for floating point ...

Some reasons for using more bits per color channel: Tetrachromats. There are rare humans with four types of cone receptors in their retinas instead of the usual three. These people can distinguish ...

The simplest method of modifying a typical DPLL-based CDCL solver is to have it output every clause it learned while deciding a formula is unsatisfiable. Such a list of clauses constitutes a RUP ...

A $k$-SAT instance over $n$ variables, monotone or otherwise, has at most $2^n - 2^{n-k}$ solutions. This is simply the number of possible settings of the $n$ variables minus the least number of ...

How do you determine what inputs you should use for a neural network? Experimentation. Initially you use a priori knowledge and intuition to guess the features will be useful for classification or ...

When you run your program its memory allocations take the form of page allocation requests to the operating system. When your program terminates, the operating system notices and returns all the ...

Your reasoning is valid, but it won't help a SAT solver go much faster. Your method produces long clauses that only forbid a single assignment. What you want to speed up a recursively searching SAT ...

The phrase is explained by the rest of the passage. I'll give a larger excerpt of the paper for context. A seminal paper by Selman, Mitchell and Levesque considered the empirical performance of ...

The congruence is true for all primes $p$ of the correct form but it is also true for some composite numbers, which makes the congruence alone useless as a primality test. Example: set $p$ to the ...

The reduction is straightforward, but what's likely tripping you up is that while 3CNF clauses seem to describe what's needed for a satisfying assignment, what they do more directly is describe what ...

Cached data about a domain for which a DNS server is not authoritative could only have come from prior recursive queries. If you send a query without the RD (recursion desired) bit set, the server is ...

Since each place in a binary number is a power of two, the binary expansion of $2^k$ for any $k$ will be a 1 followed by $k$ zeroes. Examples: $$1 = 2^0 = 1$$ 16 = 2^4 = 1\underbrace{0000}_{4\ ...

The C language standard has provisions for hosted and freestanding runtime environments and makes clear which language features are required for each. Hosted environments are required to provide the ...

A swap-with-memory instruction swaps a register's value with that of a memory location. An example of such an instruction would be the Intel 8086 XCHG instruction which can swap a register value with ...

By definition if a proof system is refutation-complete then once you've applied it to the maximum extent and not found a contradiction, you have proven that there are no refutations, i.e. the formula ...

Simplified, the operating system sees disk storage as a randomly accessible set of sectors, each sector containing some fixed number of bytes. The OS asks the disk controller for a sector using some ...

Your regular expression (a+ba*b)* won't match the string a which contains zero b's, an even number. It also won't match the strings bb or bbbb, because the expression requires one or more a's before ...

The intersection of two non-NP-hard languages can be NP-hard. Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT ...

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