MATH 470 Lecture 14

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

Cute way to state Reimann Hypothesis

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} sufficiently large, the leading half digits of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{Li}(x)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is composite, someone could just give you the factors.; EX: primality: Pratt's Theorem in which certificate is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (q_1, \ldots, q_k; a)} with primes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (q_1, \ldots, q_k)} dividing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} (checking Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{{n-1}{q_i}} \not\equiv 1 \pmod{n}} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = NP} (most believe not equal) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 ^[1] and, in fact, is NP-Complete ^[2]

Bounded Square Root mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n}

Maunders and Adleman (1978):

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b,n \in \mathbb{N}} , decide if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} has a square root mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} large prime
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} generator for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}/p\mathbb{Z})^*}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} random large integer in [2, p-2] Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c = g^\ell}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p,g,c)} are public

Transmit: send (x c^r, g^r) for some random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r \in \{ 2, \ldots, p-2 \}}

Footnotes

↑ If you find a poly-time algorithm for 3-SAT, you'll have found a poly-time algorithm for every problem in NP
↑ A problem is NP-Complete when it is in NP and NP-Hard

[1] If you find a poly-time algorithm for 3-SAT, you'll have found a poly-time algorithm for every problem in NP

[2] A problem is NP-Complete when it is in NP and NP-Hard

[1]

[2]