Data Structures and Algorithms

1407 Submissions

[2] viXra:1407.0063 [pdf] submitted on 2014-07-08 22:02:18

Polynomial Time Integer Factorization

Authors: Yuly Shipilevsky
Comments: 10 Pages.

A polynomial-time algorithm for integer factorization, wherein integer factorization reduced to a convex polynomial-time integer minimization problem
Category: Data Structures and Algorithms

[1] viXra:1407.0010 [pdf] replaced on 2014-07-04 14:06:07

A Lower Bound of 2^n Conditional Jumps for Boolean Satisfiability on A Random Access Machine

Authors: Samuel C. Hsieh
Comments: 13 Pages. This version corrects a few typing errors found in the previous version.

We establish a lower bound of 2^n conditional jumps for deciding the satisfiability of the conjunction of any two Boolean formulas from a set called a full representation of Boolean functions of n variables - a set containing a Boolean formula to represent each Boolean function of n variables. The contradiction proof first assumes that there exists a RAM program that correctly decides the satisfiability of the conjunction of any two Boolean formulas from such a set by following an execution path that includes fewer than 2^n conditional jumps. By using multiple runs of this program, with one run for each Boolean function of n variables, the proof derives a contradiction by showing that this program is unable to correctly decide the satisfiability of the conjunction of at least one pair of Boolean formulas from a full representation of n-variable Boolean functions if the program executes fewer than 2^n conditional jumps. This lower bound of 2^n conditional jumps holds for any full representation of Boolean functions of n variables, even if a full representation consists solely of minimized Boolean formulas derived by a Boolean minimization method. We discuss why the lower bound fails to hold for satisfiability of certain restricted formulas, such as 2CNF satisfiability, XOR-SAT, and HORN-SAT. We also relate the lower bound to 3CNF satisfiability.
Category: Data Structures and Algorithms