Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?
By paradoxes I mean counter intuitive results that look like a contradiction.
$\begingroup$
$\endgroup$
12
-
2$\begingroup$ Are you looking for things that feel paradox or real inconsistencies (e.g. Russell's paradox)? $\endgroup$– RaphaelCommented Nov 8, 2010 at 21:46
-
2$\begingroup$ I don't know a suitable tag for this question, maybe [big-picture] or [soft-question]. Can you give an example of math paradoxes you have mentioned so we can know what you are talking about? $\endgroup$– KavehCommented Nov 8, 2010 at 22:49
-
2$\begingroup$ Obviously, there aren't any known inconsistencies in computer science---that would be worrying. Are you just looking for counterintuitive results? Are results like the PCP theorem, Kleene's recursion theorem, and public key cryptosystems bizarre enough to count as paradoxes to you? $\endgroup$– Thomas SteinkeCommented Nov 9, 2010 at 3:38
-
4$\begingroup$ @serg, it would be really helpful if you could respond to clarify your question. Either you mean your question in a very "soft" sense that Thomas suggests - in which case the question is correctly tagged as big-picture and my answer below is off-topic, or you mean it in a somewhat technical sense ("applications and impacts of logical paradoxes in computer science") in which case your question should be tagged lo.logic, not big-picture. Or you mean something else entirely that we four commenters haven't guessed! $\endgroup$– Rob SimmonsCommented Nov 9, 2010 at 4:19
-
4$\begingroup$ Counterintuitiveness is a function of time. The fact that so many different questions are all NP-complete was undoubtedly counterintuitive before Karp's paper, as was the fact that channels have definite information capacities before Shannon's. However, now people are used to these results. $\endgroup$– Peter ShorCommented Nov 25, 2010 at 20:24
|
Show 7 more comments
13 Answers
$\begingroup$
$\endgroup$
2
I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where the running time to solve them is way better than what you would expect it to be.
-
8$\begingroup$ ditto: I've had students comment on the non-intuitveness of network flow, and even the fact that matchings can be done in poly time seems highly surprising. $\endgroup$ Commented Nov 12, 2010 at 6:16
-
9$\begingroup$ I don't quite agree. Network flow can be easily reduced to linear programming so you are claiming that linear programming being in P is counterintuitive. Perhaps. But duality shows that LP is in NP and co-NP which at least suggests that it may not be that hard. What is less intuitive is that min-cut is solvable in P because it is not naturally a "fractional" problem. $\endgroup$ Commented Oct 20, 2012 at 1:56
$\begingroup$
$\endgroup$
2
A family of counter-intuitive results is the whole "prove an upper bound to prove a lower bound" family of results. The Meyer result that $\mathsf{P} = \mathsf{NP}$ implies $\mathsf{EXP} \not\subseteq \mathsf{P}/poly$ is one example of this, and this came to my mind from both Ketan Mulmuley's GCT work as well as Ryan Williams' recent result that again used an upper bound for CIRCUIT-SAT to prove a lower bound for $\mathsf{NEXP}$ in terms of $\mathsf{ACC}$.
-
$\begingroup$ Suresh, Please provide reference to Meyer's result. $\endgroup$ Commented Nov 29, 2010 at 5:19
-
1$\begingroup$ I don't know if there's a direct reference. The Karp-Lipton paper (faculty.cs.tamu.edu/chen/courses/637/2008/pres/ashraf.pdf) credits Meyer with this result, but there's no citation. $\endgroup$ Commented Nov 29, 2010 at 6:50
$\begingroup$
$\endgroup$
2
SAT has a polynomial-time algorithm only if P=NP. We don't know whether P=NP. However, I can write down an algorithm for SAT which is polynomial-time if P=NP is true. I don't know the correct reference for this, but the wikipedia page gives such an algorithm and credits Levin.
-
5$\begingroup$ Similarly, we have a provably optimal algorithm for factoring that runs in polynomial time if factoring is in P, yet we do not know if factoring is in P (or how to analyze the runtime of this optimal function). $\endgroup$ Commented Nov 12, 2010 at 5:11
-
9$\begingroup$ This is typically referred to as "Levin universal search," and the correct reference is: L. Levin, Universal enumeration problems. Problems of Information Transmission, 9(3):265--266, 1973 (translated from Russian). This is the same paper in which Levin introduced NP-completeness (see also Cook & Karp, but as far as I know neither of them introduced the notion of an optimal universal search algorithm). The English translation can be found in Trakhtenbrot's famous survey: doi.ieeecomputersociety.org/10.1109/MAHC.1984.10036 $\endgroup$ Commented Nov 23, 2010 at 4:43
$\begingroup$
$\endgroup$
2
Computability certainly screws most students. A beautiful example with high confusion rate is this:
$f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{cases}$
Is $f$ computable?
The answer is yes; see a discussion here. Most people immediately try constructing $f$ with present knowledge. That can not work and leads to a perceived paradox which is really just subtleness.
-
7$\begingroup$ This to me seems like one of those problems where all of its trickiness is in how it's stated. This reminds me a bit of taking an algorithm, fiating that n is some constant and proclaiming that the algorithm now runs in constant time. The hard question people will typically think you're asking is whether we can write a program that will either prove pi contains a 0^n string for all n or that will determine the largest n for which it is true. $\endgroup$ Commented Nov 11, 2010 at 3:56
-
4$\begingroup$ Sure, but the fact they think like that does not illustrate trickiness the function's formulation but that people do not understand the difference between existence and construction. $\endgroup$– RaphaelCommented Nov 11, 2010 at 9:08
$\begingroup$
$\endgroup$
One surprising and counter intuitive result is that $IP = PSPACE$, proved using arithmetization around 1990.
As Arora & Barak put it (p. 157) "We know that interaction alone does not give us any languages outside NP. We also suspect that randomization alone does not add significant power to computation. So how much power could the combination of randomization and interaction provide?"
Apparently quite a bit!
$\begingroup$
$\endgroup$
How about Martin Escardo's publications showing that there are infinite sets that can be exhaustively searched over in finite time? See Escardo's guest blog post on Andrej Bauer's blog, for instance, on "Seemingly impossible functional programs".
$\begingroup$
$\endgroup$
The Recursion Theorem certainly seems counter-intuitive the first time you see it. Essentially it says that when you are describing a Turing Machine, you can assume it has access to its own description. In other words, I can build Turing Machines like:
TM M accepts n iff n is a multiple of the number of times "1" appears in the string representation of M.
TM N takes in a number n and outputs n copies of itself.
Note that the "string representation" here is not referring to the informal text description, but rather an encoding.
$\begingroup$
$\endgroup$
As Philip said, Rice's theorem is a good example: one's intuition before studying computability is that there must surely be something we can compute about computations. It turns out that we can only compute something about some computations.
$\begingroup$
$\endgroup$
Proving information-theoretic results based on complexity-theoretic assumptions is another counter-intuitive result. For instance, Bellare et al. in their paper The (True) Complexity of Statistical Zero Knowledge constructively proved that, under the certified discrete log assumption, any language that admits honest-verifier statistical zero knowledge also admits statistical zero knowledge.
The result was so odd that it surprise the authors. They pointed out this fact several times; for instance, in the introduction:
Given that statistical zero-knowledge is a computationally independent notion, it is somewhat strange that properties about it could be proved under a computational intractability assumption.
PS: A stronger result was later proved unconditionally by Okamoto (On Relationships between Statistical Zero-Knowledge Proofs).
Description of some terms
Since the above result includes a lot of cryptographic jargon, I try to informally define each term.
- Certified discrete log assumption: It is hard (for poly-size circuits) to solve the discrete logarithm, even if the group prime ($p$) is certified; that is, the factorization of $p-1$ is given.
- Zero knowledge: A protocol which yields no knowledge to polynomial-time bounded parties.
- Statistical zero knowledge: A protocol which yields no information, even to computationally unbounded parties, except with negligible probability.
- Honest-verifier zero knowledge: A protocol which yields no knowledge to polynomial-time bounded parties, if they act as specified by protocol.
$\begingroup$
$\endgroup$
How about the fact that computing permanent is #P-Complete but computing determinant - a way weirder operation happens to be in the class NC?
This seems rather strange - it did not have to be that way (or maybe it did ;-) )
$\begingroup$
$\endgroup$
2
The linear programming problem is solvable in (weakly) polynomial time. This seems very surprising: why would we be able to find one among an exponential number of vertices of a high-dimensional polytope? Why would we be able to solve a problem which is so ridiculously expressive?
Not to mention all the exponential-size linear programs which we can solved by using the ellipsoid method and separation oracles, and other methods (adding variables, etc.). For example, it's amazing that an LP with an exponential number of variables such as the Karmakar-Karp relaxation of Bin Packing can be efficiently approximated.
-
2$\begingroup$ The fact that there are exponential number of solutions is not unique to LP. Most discrete optimization problems have the same feature but they have poly-time algorithms, no? LP is a special case of convex optimization where a local optimum is a global optimum. We can also solve convex optimization modulo an epsilon issue due to irrationality and other technical reasons. For LP, due to the combinatorial structure, one can jump from this small error solution to a vertex which gives an exact solution. Equivalence of separation and optimization is surprising though. $\endgroup$ Commented Oct 20, 2012 at 18:31
-
2$\begingroup$ @ChandraChekuri what I had in mind is that a high-dimensional geometric search problem sounds like it should be hard..but of course there are also good reasons why it's not (convexity). I should probably emphasize the equivalence of separation and optimization instead. Plenty of surprising consequences there, like solving hard optimization problems on perfect graphs, for example. $\endgroup$ Commented Oct 21, 2012 at 2:33
$\begingroup$
$\endgroup$
Whenever I teach automata, I always ask my students if they find it surprising that nondeterminism doesn't add any power to finite-state automata (i.e., that for every NFA is there is an equivalent -- possibly much larger -- DFA). About half the class reports being surprised, so there you go. [I myself have lost the "feel" for what is surprising at the intro level.]
Students definitely find it surprising at first that $R\neq RE$. I challenge them to produce an algorithm that determines whether a given java program will halt, and they typically try to search for endless while loops. As soon as I show them ways of constructing loops whose termination is far from obvious, the surprise factor goes away.
$\begingroup$
$\endgroup$
I have found the A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications paradoxical, because it is a adaptive chosen ciphertext secure scheme which is homomorphic.