PSPACE completeness and Public-key cryptography
in [Theory]
|
From: Link on 8 Apr 2010 08:42 This is the html version of the file http://meami.org/custom.htm. Meami.org invoked Google to automatically generate an html version of this document as we crawled the web. Concepts, Techniques, Ideas & Proofs â Make everything as simple as possible, but not simpler.â - Albert Einstein (1879-1955) Solution exact approximate fast slow Speed âShort & sweetâ âQuick & dirtyâ âSlowly but surelyâ âToo little, too lateâ Algorithms Tradeoff: Execution speed vs. solution quality Computational Complexity Problem: Avoid getting trapped in local minima Global optimum Approximation Algorithms Idea: Some intractable problems can be efficiently approximated within close to optimal! Fast: Simple heuristics (e.g., greed) Provably-good approximations Slower: Branch-and-bound approaches Integer Linear Programming relaxation Approximation Algorithms Wishful: Simulated annealing Genetic algorithms Minimum Vertex Cover Minumum vertex cover problem: Given a graph, find a minimum set of vertices such that each edge is incident to at least one vertex of these vertices. Example: Applications: bioinformtics, communications, civil engineering, electrical engineering, etc. One of Karpâs original NP-complete problems Input graph Heuristic solution Optimal solution Minimum Vertex Cover Examples Approximate Vertex Cover Theorem: The minimum vertex cover problem is NP-complete (even in planar graphs of max degree 3). Theorem: The minimum vertex cover problem can be solved exactly within exponential time nO(1)2O(n). Theorem: The minimum vertex cover problem can not be approximated within £ 1.36*OPT unless P=NP. Theorem: The minimum vertex cover problem can be approximated (in linear time) within 2*OPT. Idea: pick an edge, add its endpoints, and repeat. Approximate Vertex Cover Algorithm: Linear time 2*OPT approximation for the minimum vertex cover problem: Pick random edge (x,y) Add {x,y} to the heuristic solution Eliminate x and y from graph Repeat until graph is empty Idea: one of {x,y} must be in any optimal solution. à Heuristic solution is no worse than 2*OPT. x y Best approximation bound known for VC! Maximum Cut Maximum cut problem: Given a graph, find a partition of the vertices maximizing the # of crossing edges. Example: Applications: VLSI circuit design, statistical physics, communication networks. One of Karpâs original NP-complete problems. A B C D E A B C D E Input graph Heuristic solution Optimal solution A B C D E cut size = 2 cut size = 4 cut size = 5 Maximum Cut Theorem [Karp, 1972]: The minimum vertex cover problem is NP-complete. Theorem: The maximum cut problem can be solved in polynomial time for planar graphs. Theorem: The maximum cut problem can not be approximated within £ 17/16*OPT unless P=NP. Theorem: The maximum cut problem can be approximated in polynomial time within 2*OPT. Theorem: The maximum cut problem can be approximated in polynomial time within 1.14*OPT. =1.0625*OPT Maximum Cut Algorithm: 2*OPT approximation for maximum cut: Start with an arbitrary node partition If moving an arbitrary node across the partition will improve the cut, then do so Repeat until no further improvement is possible Idea: final cut must contain at least half of all edges. à Heuristic solution is no worse than 2*OPT. A B C D E Input graph Heuristic solution Optimal solution cut size = 2 cut size = 3 A B C D E A B C D E cut size = 5 Approximate Traveling Salesperson Analysis: Traveling salesperson problem: given a pointset, find shortest tour that visits every point exactly once. 2*OPT metric TSP heuristic: Compute MST T = Traverse MST S = shortcut tour Output S triangle inequality! TSP minus an edge is a spanning tree S < T = MST < OPT TSP 2* 2* T covers minimum spanning tree twice Non-Approximability NP transformations typically do not preserve the approximability of the problem! Some NP-complete problems can be approximated arbitrarily close to optimal in polynomial time. Theorem: Geometric TSP can be approximated in polynomial time within (1+e)*OPT for any e>0. Other NP-complete problems can not be approximated within any constant in polynomial time (unless P=NP). Theorem: General TSP can not be approximated efficiently within K*OPT for any K>0 (unless P=NP). Graph Isomorphism Definition: two graphs G1=(V1,E1) and G2=(V2,E2) are isomorphic iff $ bijection Æ:V1®V2 such that "vi,vjÃV1 (vi,vj)ÃE1 à (Æ(vi),Æ(vj))ÃE2 Isomorphism º edge-preserving vertex permutation Problem: are two given graphs isomorphic? â Note: Graph isomorphism ÃNP, but not known to be in P â Graph Isomorphism â â â â â â Zero-Knowledge Proofs Idea: proving graph isomorphism without disclosing it! Premise: Everyone knows G1 and G2 but not â â must remain secret! Create random G â G1 Note: â is â(â) Transmit G Verifier asks for â or â Transmit â or â Verifier checks GâG1 or GâG2 Repeat k times à Probability of cheating: 2-k G1 G2 â G â â â Approximating a âproofâ! Zero-Knowledge Proofs Idea: prove graph 3-colorable without disclosing how! Premise: Everyone knows G1 but not its 3-coloring Ï which must remain secret! Create random G2 â G1 Note: 3-coloring Ï'(G2) is â(Ï(G1)) Transmit G2 Verifier asks for â or Ï' Transmit â or Ï' Verifier checks G1âG2 or Ï'(G2) Repeat k times à Probability of cheating: 2-k G1 G2 â Ï Ï Ï' Interactive proof! Zero-Knowledge Caveats Requires a good random number generator Should not use the same graph twice Graphs must be large and complex enough Ï Applications: Identification friend-or-foe (IFF) Cryptography Business transactions Zero-Knowledge Proofs Idea: prove that a Boolean formula P is satisfiable without disclosing a satisfying assignment! Premise: Everyone knows P but not its secret satisfying assignment V ! Convert P into a graph 3-colorability instance G =Æ(P) Publically Transmit Æ and G Use zero-knowledge protocol to show that G is 3-colorable à P is satisfiable iff G is 3-colorable à P is satisfiable with probability 1-2-k P = (x+y+z)(x'+y'+z)(x'+y+z') Æ G = Interactive proof! Interactive Proof Systems Prover has unbounded power and may be malicious Verifier is honest and has limited power Completeness: If a statement is true, an honest verifier will be convinced (with high prob) by an honest prover. Soundness: If a statement is false, even an omnipotent malicious prover can not convince an honest verifier that the statement is true (except with a very low probability). The induced complexity class depends on the verifierâs abilities and computational resources: Theorem: For a deterministic P-time verifier, class is NP. Def: For a probabilistic P-time verifier, induced class is IP. Theorem [Shamir, 1992]: IP = PSPACE 2-SAT 2-Way automata 3-colorability 3-SAT Abstract complexity Acceptance Ada Lovelace Algebraic numbers Algorithms Algorithms as strings Alice in Wonderland Alphabets Alternation Ambiguity Ambiguous grammars Analog computing Anisohedral tilings Aperiodic tilings Approximate min cut Approximate TSP Concepts, Techniques, Idea & Proofs Approximate vertex cover Approximations Artificial intelligence Asimovâs laws of robotics Asymptotics Automatic theorem proving Autonomous vehicles Axiom of choice Axiomatic method Axiomatic system Babbageâs analytical engine Babbageâs difference engine Bin packing Binary vs. unary Bletchley Park Bloom axioms Boolean algebra Boolean functions Bridges of Konigsberg Brute fore Busy beaver problem C programs Canonical order Cantor dust Cantor set Cantorâs paradox CAPCHA Cardinality arguments Cartesian coordinates Cellular automata Chaos Chatterbots Chess-playing programs Chinese room Chomsky hierarchy Chomsky normal form Chomskyan linguistics Christofidesâ heuristic Church-Turing thesis Clay Mathematics Institute Clique problem Cloaking devices Closure properties Cogito ergo sum Colorings Commutativity Complementation Completeness Complexity classes Complexity gaps Complexity Zoo Compositions Compound pendulums Compressibility Computable functions Computable numbers Computation and physics Computation models Computational complexity Concepts, Techniques, Ideas & Proofs Computational universality Computer viruses Concatenation Co-NP Consciousness and sentience Consistency of axioms Constructions Context free grammars Context free languages Context sensitive grammars Context sensitive languages Continuity Continuum hypothesis Contradiction Contrapositive Cookâs theorem Countability Counter automata Counter example Cross- product Crossing sequences Cross-product construction Cryptography DARPA Grand Challenge DARPA Math Challenges De Morganâs law Decidability Deciders vs. recognizers Decimal number system Decision vs. optimization Dedekind cut Denseness of hierarchies Derivations Descriptive complexity Diagonalization Digital circuits Diophantine equations Disorder DNA computing Domains and ranges Dovetailing DSPACE DTIME EDVAC Elegance in proof Encodings Enigma cipher Entropy Enumeration Epsilon transitions Equivalence relation Euclidâs âElementsâ Euclidâs axioms Euclidean geometry Eulerâs formula Eulerâs identity Eulerian tour Existence proofs Exoskeletons Exponential growth Concepts, Techniques, Ideas & Proofs Exponentiation EXPSPACE EXPSPACE EXPSPACE complete EXPTIME EXPTIME complete Extended Chomsky hierarchy Fermatâs last theorem Fibonacci numbers Final states Finite automata Finite automata minimization Fixed-point theorem Formal languages Formalizations Four color problem Fractal art Fractals Functional programming Fundamental thm of Algebra Fundamental thm of Arith. Gadget-based proofs Game of life Game theory Game trees Gap theorems Garey & Johnson General grammars Generalized colorability Generalized finite automata Generalized numbers Generalized venn diagrams Generative grammars Genetic algorithms Geometric / picture proofs Godel numbering Godelâs theorem Goldbachâs conjecture Golden ratio Grammar equivalence Grammars Grammars as computers Graph cliques Graph colorability Graph isomorphism Graph theory Graphs Graphs as relations Gravitational systems Greibach normal form âGrey gooâ Guess-and-verify Halting problem Hamiltonian cycle Hardness Heuristics Hierarchy theorems Hilbertâs 23 problems Hilbertâs program Hilbertâs tenth problem Concepts, Techniques, Ideas & Proofs Historical perspectives Household robots Hung state Hydraulic computers Hyper computation Hyperbolic geometry Hypernumbers Identities Immermanâs Theorem Incompleteness Incompressibility Independence of axioms Independent set problem Induction & its drawbacks Infinite hotels & applications Infinite loops Infinity hierarchy Information theory Inherent ambiguity Initial state Intelligence and mind Interactive proofs Intractability Irrational numbers JFLAP Karpâs paper Kissing number Kleene closure Knapsack problem Lambda calculus Language equivalence Law of accelerating returns Law of the excluded middle Lego computers Lexicographic order Linear-bounded automata Local minima LOGSPACE Low-deg graph colorability Machine enhancements Machine equivalence Mandelbrot set Manhattan project Many-one reduction Matiyasevichâs theorem Mechanical calculator Mechanical computers Memes Mental poker Meta-mathematics Millennium Prize Minimal grammars Minimum cut Modeling Multiple heads Multiple tapes Mu-recursive functions MAD policy Nanotechnology Natural languages Concepts, Techniques, Ideas & Proofs Navier-Stokes equations Neural networks Newtonian mechanics NLOGSPACE Non-approximability Non-closures Non-determinism Non-Euclidean geometry Non-existence proofs NP NP completeness NP-hard NSPACE NTIME Occamâs razor Octonions One-to-one correspondence Open problems Oracles P completeness P vs. NP Parallel postulate Parallel simulation Dovetailing simulation Parallelism Parity Parsing Partition problem Paths in graphs Peano arithmetic Penrose tilings Physics analogies Pi formulas Pigeon-hole principle Pilotless planes Pinwheel tilings Planar graph colorability Planarity testing Polyaâs âHow to Solve Itâ Polyhedral dissections Polynomial hierarchy Polynomial-time P-time reductions Positional # system Power sets Powerset construction Predicate calculus Predicate logic Prime numbers Principia Mathematica Probabilistic TMs Proof theory Propositional logic PSPACE PSPACE completeness Public-key cryptography Pumping theorems Pushdown automata Puzzle solvers Pythagorean theorem Concepts, Techniques, Ideas & Proofs Quantifiers Quantum computing Quantum mechanics Quaternions Queue automata Quine Ramanujan identities Ramsey theory Randomness Rational numbers Real numbers Reality surpassing Sci-Fi Recognition and enumeration Recursion theorem Recursive function theory Recursive functions Reducibilities Reductions Regular expressions Regular languages Rejection Relations Relativity theory Relativization Resource-bounded comput. Respect for the definitions Reusability of space Reversal Reverse Turing test Riceâs Theorem Riemann hypothesis Riemannâs zeta function Robots in fiction Robustness of P and NP Russellâs paradox Satisfiability Savitchâs theorem Schmitt-Conway biprism Scientific method Sedenions Self compilation Self reproduction Set cover problem Set difference Set identities Set theory Shannon limit Sieve of Eratosthenes Simulated annealing Simulation Skepticism Soundness Space filling polyhedra Space hierarchy Spanning trees Speedup theorems Sphere packing Spherical geometry Standard model State minimization Concepts, Techniques, Ideas & Proofs Steiner tree Stirlingâs formula Stored progam String theory Strings Strong AI hypothesis Superposition Super-states Surcomplex numbers Surreal numbers Symbolic logic Symmetric closure Symmetric venn diagrams Technological singularity Theory-reality chasms Thermodynamics Time hierarchy Time/space tradeoff Tinker Toy computers Tractability Tradeoffs Transcendental numbers Transfinite arithmetic Transformations Transition function Transitive closure Transitivity Traveling salesperson Triangle inequality Turbulance Turing complete Turing degrees Turing jump Turing machines Turing recognizable Turing reduction Turing test Two-way automata Type errors Uncomputability Uncomputable functions Uncomputable numbers Uncountability Undecidability Universal Turing machine Venn diagrams Vertex cover Von Neumann architecture Von Neumann bottleneck Wang tiles & cubes Zero-knowledge protocols .. .. .. ..
|
Pages: 1 Prev: Plot Graph Matrix Next: Geometric TSP can be approximated |