# 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