MATH 470 Lecture 14

« previous | Tuesday, February 26, 2013 | next »

Cute way to state Reimann Hypothesis

For $x$ sufficiently large, the leading half digits of $\mathrm {Li} (x)$ and $\pi (x)$ agree

Complexity Summary

Each branch of the following tree represents "is a subset of"

P
`-- ZPP
    `-- RP
        |-- NP
        |   `-- NPC
        `-- BPP
            `-- BQP

Properness of any inclusion here (that is, whether equality could be a possibility) is unknown: The classic P = NP problem!

By the way, all are subsets of exponential time

P

Polynomial Time

Family of decision problems doable in time polynomial to the input size

EX: existence of square root mod prime $p$

ZPP

Zero-Error Probability Polynomial Time

"Las Vegas Algorithms" (uses chance, but supposedly doesn't cheat you)

{{ P }} via a randomized algorithm which says: "correct answer" (Pr ≥ 0.5) or "run me again" (Pr ≤ 0.5)

RP

Randomized Polynomial Time

"Monte Carlo Algorithms"

{{ P }} via a randomized algorithm for which "yes" is always correct, but "no" is wrong with Pr ≤ 0.5

EX: compositeness testing via Solovay-Strassen.

NP

Non-Deterministic Polynomial Time

NOT' "not P"

Family of decision problems where a "yes" answer (certificate) can be checked in polynomial time

EX: compositeness: to check whether $n$ is composite, someone could just give you the factors.

EX: primality: Pratt's Theorem in which certificate is $(q_{1},\ldots ,q_{k};a)$ with primes $(q_{1},\ldots ,q_{k})$ dividing $n-1$ (checking $a^{{n-1}{q_{i}}}\not \equiv 1{\pmod {n}}$ for $i\in [1,k]$)

EX: #NP-Completeness

BPP

Bounded-Error Probability Polynomial Time

"Evil cousin of ZPP"

{{ P }} via a randomized algorithm which yields correct answers with Pr ≥ 0.75

BQP

Bounded-Error Probability Quantum Polynomial Time

Family of Enumerative problems doable in polynomial time to the input size on a quantum computer.

EX: Factoring and Discrete Logarithm (Shor, 1994)

Biggest Open Problems

$P=NP$ (most believe not equal) $P=BPP$ (most believe equal)

More on Primality

• Pratt (1977) showed that primality is in NP
• Adleman and Huang (1992) showed that primality is in RP with use of algebraic curves (Yes: always right, no: wrong Pr ≤ 0.5)
• Adleman-Huang + Solovay-Strassen shows that primality is in ZPP

NP-Completeness

3-SAT

(See CSCE 411 Lecture 32#3SAT→)

Cook's Theorem (1972): 3-SAT is NP-Hard and, in fact, is NP-Complete

Bounded Square Root mod $n$

Maunders and Adleman (1978):

Given $a,b,n\in \mathbb {N}$, decide if $a$ has a square root mod $n\in [1,b]$.

Impaglizzo's Five Worlds

Algorithmica

If P = NP, tasks requiring creativity could potentially be automated

Heuristica

IF P ≠ NP, but we can solve most NP-Complete problems in poly-time (for only a few special cases)

Pessiland

P = NP and there are no 1-way functions

if every function is reversible, then no cryptography

Cryptomania

Factoring large integers is hard on average (and so are discrete logarithms and ....)

Good for cryptographers

Minicrypt

...

Paranoia

The NSA has a quantum computer...

Weirdland

We find a poly algorithm for 3-SAT, but it runs in $O(n^{10^{5000000}})$

Audio Encryption

In practice, for audio signals, we use different techniques that what we've covered so far

AN/PRC-148 Multiband Team Radio Uses Triple-DES because it's fast.

RSA is most often used for (secret) key transmission and digital signatures for integrity/authorization

El Gamal

• $p$ large prime
• $g$ generator for $(\mathbb {Z} /p\mathbb {Z} )^{*}$

$\ell$ random large integer in [2, p-2] $c=g^{\ell }$

$(p,g,c)$ are public

Transmit: send (x c^r, g^r) for some random $r\in \{2,\ldots ,p-2\}$