```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


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




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
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.
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
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


Wikipedia, The Free Encyclopedia, ``Complexity classes P and NP.’’
Introductory


S. Baase, Computer Algorithms: Introduction to Design and Analysis,
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,
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



…
…
…
```