Kyle Jones
  • Member for 9 years, 10 months
  • Last seen this week
  • Seattle, WA
$NP \ vs \ co-NP$: tautology to SAT and vice versa?
Accepted answer
3 votes

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

View answer
GOTO vs. including line in loop - will it affect efficiency?
2 votes

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

View answer
Modeling tiling problems as SAT problems
2 votes

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

View answer
Is finding arbitrary length cycles in a graph NP-Hard?
Accepted answer
3 votes

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

View answer
Reducing "multiple satisfiability" to normal SAT
Accepted answer
0 votes

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

View answer
Are there lossless data compression techniques that do not exploit repetitive patterns?
3 votes

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

View answer
Best improvements to do to the DPLL SAT algorithm
Accepted answer
2 votes

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

View answer
Is converting boolean formulas to sum-of-products a hard problem?
Accepted answer
1 votes

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

View answer
How to choose between UC and PL when using the DPLL algorithm?
3 votes

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

View answer
what is a compiler intrinsic function?
5 votes

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

View answer
What's the point of 48 bit colour?
Accepted answer
5 votes

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

View answer
How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances?
3 votes

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

View answer
Upper bound for #Monotone k-SAT
Accepted answer
2 votes

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

View answer
How do you determine the inputs to a neural network?
Accepted answer
3 votes

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

View answer
Does the memory get unallocated when program exits?
Accepted answer
2 votes

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

View answer
Conflict Driven Clause Learning combined with brute force
Accepted answer
5 votes

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

View answer
What's non-algorithm-specific
Accepted answer
3 votes

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

View answer
Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?
3 votes

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

View answer
Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT
2 votes

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

View answer
Do iterative DNS queries return results from the servers cache?
1 votes

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

View answer
What this subnetting restriction means
Accepted answer
1 votes

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

View answer
use of C library in operating systems
3 votes

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

View answer
What is a swap-with-memory instruction?
Accepted answer
3 votes

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

View answer
What can be concluded from a full application of resolution?
3 votes

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

View answer
How does a hard drive knows what bit is the beginning of of a byte/word?
Accepted answer
2 votes

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

View answer
Difference between the two regular expression
Accepted answer
2 votes

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

View answer
Are NP-complete sets formed from two other sets only if at least one is NP-hard?
1 votes

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

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