𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Self-witnessing polynomial-time complexity and prime factorization

✍ Scribed by Michael R. Fellows; Neal Koblitz

Publisher
Springer
Year
1992
Tongue
English
Weight
295 KB
Volume
2
Category
Article
ISSN
0925-1022

No coin nor oath required. For personal study only.

✦ Synopsis

Abstracl. For a number of computational search problems, the existence of a polynomial-time algorithm for the problem implies that a polynomial-time algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-lime complexity are presented. Our main resuk demonstrates this property for the problem of computing the prime factorization of a positive integer, based on a lemma which shows that a certificate for primality or compositeness can be constructed for a positive integer p in deterministic polynomial time given a complete facterization ofp -i.

πŸ“œ SIMILAR VOLUMES

A Note on Exponential Polynomials and Pr
A Note on Exponential Polynomials and Prime Factors
✍ Rod McBeth πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 128 KB

A NOTE ON EXPONENTIAL POLYNOMIALS AND PRIME FACTORS by ROD MCBETH in London (England) Let p,, p 2 , p 3 , . . . denote the progression 2 , 3 , 5 , . . . of primes. The polynomials f of the class EP given in [l] can be correlated with functions p ( f ; -) which are based on the above progression. The

Polynomial Time Algorithms to Approximat
Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
✍ Alexander Barvinok πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 308 KB

We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high prob