Computationally Intractable Problems in Communication Speaker Yu Jia Yuan April 19, 2004 Motivation – The one million dollar question Can we solve every problem in digital communications by designing an algorithm? Can we find a counter-example? From an engineering perspective, can we solve these problems “efficiently”? There is a prize for answering this question worth no less than one million dollars! Outline – Main ideas Problems & algorithms in computer science terms. Computational complexity classes. Why are they useful? Examples of ``hard’’ problems in communications. How to deal with them. This presentation may seem long because many unfamiliar concepts are explained. Related secondary ideas Communication complexity classes, as opposed to computational time complexity classes. More on toward end of presentation. Philosophical question on the complexity of communication. An example is coming up. Two-army problem Messenger Red Army Bob Blue Army Red Army Alice Worked-out example Messenger 1 Red Army Bob Messenger 2 Blue Army Red Army Alice Two-army – Remarks Analogy to communications Particularly to Networking problems Communication can be very complex Some tasks are even impossible In those cases, we usually look for solutions that are good enough NP-complete problems Main event of this presentation Complexity theory jargon What do we mean by a hard problem? What is a fast algorithm? The difference between easy and hard problems, or between fast and slow algorithms is the difference between polynomial-time and not polynomialtime. Definitions For an algorithm For a problem A running time polynomially upper bounded in the input size means fast or efficient. Otherwise, it is slow or inefficient. A guaranteed solution with a fast algorithm for any instance of the problem means easy. Otherwise, it is hard. Different degrees of hardness Undecidable Provably intractable NP-complete, NP-hard (apparently intractable, but no guarantee) Language & Turing-machine Formalism Defining the complexity classes using mathematical objects (languages, Turing machines). A problem is NP-hard means that its corresponding decision problem is NP-complete. General problems Algorithms Polynomialtime reduction Decision problems Turing machines Encode instance into strings Language recognition What are complexity classes? The world of complexity classes What are complexity classes? P contains problems such as: NP-complete problems contains hundred of problems: Matrix inversion, DFT, Sorting, Shortest path through a trellis. Traveling salesman, CLIQUE, Graph k-coloring, etc. In the ``gray’’ zone between P and NPcomplete: Integer factorization. What are they good for? To make the fundamental distinction between polynomial and exponential time complexity. For proving that solving any NPcomplete problem solves all 300 of them! Examples in Communications Some we have already encountered: Error-correcting codes Multiuser detection in CDMA Others: Integer factorization ML sequence detection for ISI channel (Viterbi algorithm on ``exponential’’ trellis) The Party problem Recall the friendship graph problem in assignment 1? Why was it ever asked? The relation with communications is not obvious. NP-completeness Ramsey numbers Party problem Clique Error-correcting codes The party problem & Ramsey numbers The party problem asks for the minimum number of guests that must be invited R(m,n) so that: at least m will know each other, or at least n will not know each other. R(3,3) = 6. R(4,4) = 18. It is extremely difficult to find larger Ramsey numbers R(5,5), R(6,6). Graphical formulation It turns out that finding the Ramsey number R(m,n) is equivalent to a graph problem. Definition. A clique of a graph is its maximal complete subgraph. A complete has an edge connecting every pair of vertices. A graph may have multiple cliques. Finding Ramsey numbers Find the minimum number of vertices R(m,n) such that any undirected, simple graph of order R(m,n) contains a clique of order m, or its complement contains a clique of order n. Simple graph: loops and parallel edges forbidden. Order of a graph: its number of vertices. Complement: connect non-adjacent vertices & vice versa Theorem. Determining whether an arbitrary undirected graph contains a clique of size m is NPhard. Hence, finding Ramsey number for general m and n is also NP-hard. Relation with error-correcting codes Represent all strings of length n (over finite field) as vertices. Draw edges on vertices with dHamming(u,v) > d The largest code of length n with minimum distance d is a clique. This problem is NP-hard. Multiuser detection in CDMA Assumptions. Synchronous system, AWGN, equiprobable symbols bk. r = RA b + n Jointly optimal multiuser detection decision rule: b* = arg min { bT ARA b – 2bT A r } Verdu showed that MUD is NP-hard by polynomial-time reduction to PARTITION. Alternative: reduction to QUADRATIC PROGRAMMING What to do when an efficient algorithm cannot be found? Show that it is computationally intractable. What does it NP-completeness tell us? Such a problem cannot be solved by efficient means unless a major breakthrough were to occur. Most researchers publicly speculate that efficient algorithms do not exist for these problems. Options Change the original problem Efficient algorithms for special cases of the general problem Randomized, Evolutionary and Quantum algorithms Not strictly speaking ‘efficient’, but run quickly most of the time e.g. Simulated annealing in-class example Shor’s algorithm for integer factorization with a quantum computer Find approximate solutions Greedy algorithm for KNAPSACK Communication complexity classes Communication complexity classes indicate the amount of communication needed to solve a problem when the input is distributed among multiple machines, as in parallel computing. Introduced by Babai, Frankl, and Simon (1986) to extend the notion of computational time complexity classes Final thoughts I gave only an overview of complexity questions in communication. I left out all the formal definitions in the hope that it would be more informative. For all the gory details on the topic of NP-completeness, I invite you to take a look at my report, or at one of the following references. References 5-minute reading Wikipedia, The Free Encyclopedia, ``Complexity classes P and NP.’’ Introductory S. Baase, Computer Algorithms: Introduction to Design and Analysis, first edition, Addison-Wesley, 1978. Comprehensive M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. CSC 364S Notes, http://www.cs.toronto.edu/~sacook/csc364h/ An Annotated List of Selected NP-complete Problems, http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html Article on Millenium Prize S. Cook, ``The P versus NP Problem,’’ Manuscript prepared for the Clay Mathematics Institute for the Millennium Prize Problems, April 2000 (revised November 2000). References Communications-related E. Berlekamp, R. McEliece, H. van Tilborg, ``On the inherent intractability of certain coding problems,’’ IEEE Trans. on Information Theory, vol. 24, no. 3, pp. 384-386, May 1978. S. Verdú, ``Computational Complexity of Optimum Multiuser Detection,’’ Algorithmica, vol. 4, no. 3, pp. 303312, 1989. C. Sankaran, A. Ephremides, ``Solving a class of optimum multiuser detection problems with polynomial complexity,’’ IEEE Trans. on Information Theory, vol. 44 , no. 5 , pp. 1958-1961, Sept. 1998. S. A. Burr, ``Determining Generalized Ramsey Numbers is NP-hard,’’ Ars Combinatoria 17 (1984), 21--25. Question Period … … …

Descargar
# Complexity & Communication