More tender nuggets
You asked for ’em, you got ’em. (Do you want fries with that?)
- Suppose a baby is given some random examples of grammatical and ungrammatical sentences, and based on that, it wants to infer the general rule for whether or not a given sentence is grammatical. If the baby can do this with reasonable accuracy and in a reasonable amount of time, for any “regular grammar” (the very simplest type of grammar studied by Noam Chomsky), then that baby can also break the RSA cryptosystem.
- Oded Regev recently invented a public-key cryptosystem with an interesting property: though it’s purely classical, his system only known to be secure under the assumption that certain problems are hard for quantum computers. The upside is that, if these problems are hard for quantum computers, then Regev’s system (unlike RSA) is also secure against attack by quantum computers!
- Suppose N boys and N girls join a dating service. We write down an N-by-N matrix, where the (i,j) entry equals 1 if the ith boy and the jth girl are willing to date each other, and 0 if they aren’t. We want to know if it’s possible to pair off every boy and girl with a willing partner. Here’s a simple way to find out: first rescale every row of the matrix to sum to 1. Then rescale every column to sum to 1. Then rescale every row, then rescale every column, and so on N5 times. If at the end of this scaling process, every row and column sum is between 1-1/N and 1+1/N, then it’s possible to pair off the boys and girls; otherwise it isn’t.
- If two graphs are isomorphic, then a short and simple proof of that fact is just the isomorphism itself. But what if two graphs aren’t isomorphic? Is there also a short proof of that — one that doesn’t require checking every possible way of matching up the vertices? Under a plausible assumption, we now know that there is such a proof, for any pair of non-isomorphic graphs whatsoever (even with the same eigenvalue spectrum, etc). What’s the plausible assumption? It has nothing to do with graphs! Roughly, it’s that a certain problem, which is known to take exponential time for any one algorithm, still takes exponential time for any infinite sequence of algorithms.
- Suppose we had a small “neural network” with only three or four layers of neurons between the input and output, where the only thing each neuron could do was to compute the sum of its input signals modulo 2. We can prove, not surprisingly, that such a neural net would be extremely limited in its power. Ditto if we replace the 2 by 3, 4, 5, 7, 8, 9, or 11. But if we replace the 2 by 6, 10, or 12, then we no longer know anything! For all we know, a three-layer neural network, composed entirely of “mod 6 neurons,” could solve NP-complete problems in polynomial time.
Follow
Comment #1 November 3rd, 2006 at 7:44 am
>> For all we know, a three-layer neural network, composed entirely of “mod 6 neurons,” could solve NP-complete problems in polynomial time.
So why aren’t people …?
Comment #2 November 3rd, 2006 at 8:42 am
For one thing, our neurons aren’t mod 6. 🙂
Comment #3 November 3rd, 2006 at 8:51 am
Mmmm, those be some tasty nuggets
Comment #4 November 3rd, 2006 at 10:35 am
system only known to be secure under the assumption that certain problems are hard for quantum computers. The upside is that, if these problems are hard for quantum computers, then Regev’s system (unlike RSA) is also secure against attack by quantum computers!
What’s the difference between being “secure under the assumption that certain problems are hard for QCs” and being “secure against attack by QCs” ?
Comment #5 November 3rd, 2006 at 10:39 am
I mean… why aren’t people researching neural networks mod 6 to solve NP-complete problems? ^.^
Comment #6 November 3rd, 2006 at 11:00 am
What’s the difference between being “secure under the assumption that certain problems are hard for QCs” and being “secure against attack by QCs” ?
It’s a subtle point: the reduction from the problem in question to breaking the cryptosystem is a quantum reduction. So, even if all you wanted was security against classical attacks, you would still need to assume the problem was hard for QC’s. That you also get security against quantum attacks is sort of a free bonus.
Comment #7 November 3rd, 2006 at 11:06 am
I mean… why aren’t people researching neural networks mod 6 to solve NP-complete problems?
No one believes they actually exist. People have been trying to rule them out — that’s been an open problem since the 80’s, and is sometimes invoked as an example of how meager our circuit lower bounds really are.
If you’re planning to look for these things, I suggest you first prove NP is in P/poly — that would be a necessary first step! 🙂
Comment #8 November 3rd, 2006 at 11:27 am
actually, there is a zero-th step: understand what P/poly is. I’ll read again this night the 6th chapter of Sanjeev Arora and Boaz Barak and try to understand this time. ^.^
Comment #9 November 3rd, 2006 at 11:35 am
Is not the claim in point 1 based on the assumption that babies brains are a particular sort of computer model? A assumption that is, how shall we say it, wrong?
Comment #10 November 3rd, 2006 at 11:40 am
No, Johan, you miss the point.
The point is that any given RSA cryptosystem problem can be translated into a regular grammar problem. So if the baby can always solve regular grammar problems correctly, you take the RSA problem you want to solve, translate it into a regular grammar problem, and hand it to the baby.
Comment #11 November 3rd, 2006 at 11:44 am
Language acquisition does not mean to infer a set of production rules from a small set of examples. It is possible precisely because of the fact that human languages are not generated by arbitrary context-free grammars, but only by very special ones with a limited set of parameters that can be varied.
I doubt very much that a baby could learn an arbitrary regular language at the same rate as it might acquire a human language.
Comment #12 November 3rd, 2006 at 11:45 am
anonymous: Yes, that’s exactly the upshot!
Comment #13 November 3rd, 2006 at 5:42 pm
Along the lines of the bin-packing nugget.. has anyone tried to make a really appealing demo of the NP-completeness concept, in the form of, say, a video game, which if you could beat it would generate as a byproduct a solution to a meaningful and seemingly unrelated math problem?
As distributed computing projects go it would probably be wasteful, but as PR.. who knows?
Or, reduce the problem of finding a 100-line proof of P != NP to a huge jigsaw problem, and offer a million dollars (via Clay Inst.) to solve. I recall that another jigsaw prize challenge created lots of interest (link?).
Comment #14 November 3rd, 2006 at 7:16 pm
The MOD 6: There is a difference
between what we can PROVE and
what we thing is TRUE.
We can PROVE stuff for mod p
where p is prime.
Although we can’t PROVE stuff for
mod 6, I don’t know of anyone
who really things SAT is in
Neural net with MOD 6 ops.
Then again, I would have told you
20 years ago that OF COURSE
bounded width branching programs
form a hierachy, they don’t all
collpase to width 5. (poly length)
bill g.
Comment #15 November 3rd, 2006 at 8:20 pm
andy d: That’s a fantastic idea! Let’s (as a community) put it on our to-do list!
Comment #16 November 4th, 2006 at 9:14 am
@the videogame idea
Thats a totally kickass suggestion Andy. I dont know about the jigwaw, but Luis von Ahn has done something along these lines with captcha or one of its sister projects.
In fact, if the P=NP space is too large to be feasible, one could try the NP-but-not-known-NP-complete variety. Proof/Disproof by witness can ensue.
Scott – any comment on size of the combinatorial space for popular problems like factorization? How many players would need to make how many moves for how long before we strike gold?
Comment #17 November 4th, 2006 at 9:17 am
Sorry, correction. Factorization is known to be P thanks to Agrawal and company.
Yea scott i know i have footinmouthitis 🙂
Comment #18 November 4th, 2006 at 10:34 am
Great choice, Scott
can you add some links/references?
Comment #19 November 4th, 2006 at 6:08 pm
Uh, thanks for the feedback.. any volunteers?
Just so everyone’s clear, the challenge isn’t to show a video game can be NP-hard–that’s been accomplished: Minesweeper, Tetris, Sokoban… you could do it for Mario Bros.
The challenge would making a game where the source math problems are substantial, yet the game instances they reduce to are entertaining and potentially solvable given human abilities. As with the babies example, even crack gamers can’t just beat anything you hand to them in the form of a game.
One additional point: ideally the source problem would be an optimization problem and the reduction would be a robust one, where higher and higher (not necessarily perfect) scores in the game bring better and better solutions to the source problem. There are examples of this kind of reduction.
Comment #20 November 4th, 2006 at 6:26 pm
what do you think, scott:
Assumed NP-complete problems have polynomial size- circuits. Doesn’t it seem to be impossible to proove P!=NP then? Because a TM that actually produces the circuits (in P) might be arbitrary long.
Comment #21 November 4th, 2006 at 7:17 pm
Andy, the suggestion of reducing math problems to video games for the sake of PR is a great one, but you seem to be going even further and suggesting this may actually be an approach to solving those problems? Hoping that a heuristic for a problem can benefit by throwing the structure of the problem away… Way to go – that’s the kind of counter-intuitive thinking that makes it such fun to be a computer scientist!
Of course, the worst-case scenario would be if someone takes the suggestion seriously and actually solves P vs NP that way. Time then for complexity theorists to commit hara-kiri…
Comment #22 November 4th, 2006 at 7:17 pm
if the circuits have no structure whatsoever (besides being polynomial)
Comment #23 November 4th, 2006 at 8:44 pm
Cheshire Cat–I’ve thought about the kind of project you refer to, but I wouldn’t bank on it anytime soon. (And for the record, I don’t think humans can reliably solve NP-hard problems, in any format.)
I would really just like to see a game where you can view, and possibly pose, modest-sized but not trivial math problems in some domain, and then have them translated into something more entertaining. Hopefully it would enable skilled gamers to solve problems that would otherwise stump them or appear too tedious.
Comment #24 November 4th, 2006 at 10:11 pm
Assumed NP-complete problems have polynomial size- circuits. Doesn’t it seem to be impossible to proove P!=NP then? Because a TM that actually produces the circuits (in P) might be arbitrary long.
No. Assuming NP is in P/poly, it’s still consistent with everything we know that P!=NP and that that’s provable. The proof would just have to make essential use of uniformity.
Comment #25 November 4th, 2006 at 11:35 pm
Can you give references for these claims? (Not because I doubt you, but because I want to read about them.)
Comment #26 November 4th, 2006 at 11:37 pm
I’m a little confused about claim 1. So, presuming that babies do in fact learn correct grammar (before starting formal study of grammar in school) what are we left to conclude?
– Language ruless are simpler than regular grammars?
– The sentences parents speak to their child are more structured than we think?
– Babies can break the RSA cryptoystem?
Comment #27 November 5th, 2006 at 1:38 am
Alright, alright:
1. Kearns & Valiant (see also de Wolf)
2. Regev
3. Lecture by Avi Wigderson. See also paper by Linial, Samorodnitsky, and Wigderson
4. Klivans & van Melkebeek
5. Many papers have discussed the mod 6 gates issue; see this one for example
Comment #28 November 5th, 2006 at 1:39 am
@andy d
Im a little confused.
Are you thinking of using the game as some kind of Genetic Algo that searches for the globally optimum solution to a problem? Lots of players making “noisy”, possibly illogical moves and scanning a huge search space which would otherwise be mostly unexplored?
Comment #29 November 5th, 2006 at 1:42 am
I’m a little confused about claim 1. So, presuming that babies do in fact learn correct grammar (before starting formal study of grammar in school) what are we left to conclude?
– Language ruless are simpler than regular grammars?
– The sentences parents speak to their child are more structured than we think?
– Babies can break the RSA cryptoystem?
This question was discussed and answered earlier. The key point is that human beings share a universal grammar — i.e. one that’s hardwired into the brain — with only a small number of “parameter settings” that need to be learned. For more, see Ronald de Wolf’s master’s thesis (linked to above), or read The Language Instinct by Steven Pinker.
Comment #30 November 6th, 2006 at 11:04 am
Linial, Samorodnitsky, and Wigderson give an approximate algorithm for calculating matrix permanents. Do you know if this (or a related) algorithm has been used to numerically calculate quantum statistical properties of bosonic systems, which involve matrix permanents?
P.S. Do you know why Citeseer seems to be down every other time I try to use it? With multiple mirrors being down at the same time? I don’t understand why computer scientists can’t achieve the same reliability as the physics arXiv.
Comment #31 November 8th, 2006 at 5:38 pm
Snehit, that’s not true.
Agrawal etc. proved PRIMES is in P, not FACTORIZATION. Different problem.
Comment #32 November 14th, 2006 at 6:55 am
Regarding the idea discussed here of getting humans to solve NP-hard problems — not exactly the same, but along similar lines:
http://www.cis.upenn.edu/~mkearns/papers/ScienceFinal.pdf
Best
Michael Kearns
Comment #33 December 11th, 2006 at 3:29 pm
[…] I just discovered a new blog, Shtetl-Optimized, for your consideration. […]
Comment #34 December 21st, 2006 at 5:20 pm
So, although, I appreciate these ‘insites’, i also realize this is a blog, and to be credited in any fashion, cite sources of any ideas or related concepts.
I am familiar with a few of these nuggets, but it’s not the point for a person not knowing. Citing also adds further research one could do on the subjects as they find interesting. it’s win-win…