That article is now linked to on Wikipedia and (much to my surprise) has come to be the AUTHORITY on what people were thinking then.
TEN years have passed! It is time to take the pulse of the community again. Hence I will ONCE AGAIN (!) be conducting a poll to appear in a SIGACT News Complexity Column.
SO- I would like you to email gasarch@cs.umd.edu (in LaTeX or plaintext) the answers to the questions below. (Comments to the blog will not be counted as answering the poll.) I would like to get this poll written this summer, so I will give a deadline of October 31, 2011. (I may extend this if I do not have enough responses.)
- Do you think P=NP or not? You may give other answers as well.
- When do you think it will be resolved?
- What kinds of techniques do you think will be used?
- Will the problem still be relevant given advances in algorithms and in SAT Solvers?
- Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem.
- Do I have your permission to print your response? I will do this for some people--- how many depends on how many answer the poll.
- What is your highest degree in and where is it from? This information will be used for statistics only.
Can non-theory CSists participate?
ReplyDeletei hope so, a non cs solved it yesterday
Deletei hope so, a guess was submitted yesterday and theres a lot of buzz
Delete-anon
-----------
ReplyDeleteDoes P=NP or not?
• Yes
• No
• Undecidable
• Ill-posed
-----------
Molly Fortnow's post from 2050:
Back in the early 21st century, my father Lance and his great friend Bill GASARCH regularly polled complexity theorists with regard to the question "Does P=NP or not?"
Nowadays in 2050, we appreciate that the answer depends on the complexity-theoretic axioms and definitions embraced. In the now-most-popular axiom set ZFH/CV (Zermalo-Frankel-Hartmanis, with the Axiom of Choice and the Requirement of Algorithm Verifiability), it has been rigorously proved that P'≠NP'.
In the broader universe of ZF/C, the P versus NP problem has been proved to be formally undecidable; the intuition being that the undecidable runtime attributes of P are insurmountable obstructions to decidability.
Nowadays in 2050, concrete one-way functions are in widespread use, whose inverses provably can be efficiently computed (if at all) only by algorithms whose correctness cannot be verified within ZF/C. The implications of this finding for cryptographic security are the subject of ongoing (mainly philosophical) debate.
Recent polls show that practicing computer scientists prefer to work in ZFH/CV, rather than ZF/C, by a three-to-one proportion; the most popular reason being that "ZFH/CV proves more cool theorems and points to stronger practical algorithms."
1) Anon: YES, non-CSists can participate.
ReplyDeleteThis is why its important to say what you degree you have and what its in so I can say thing like
80% of all theatre major think that P vs NP is ind of ZFC.
2) John S- I will answer the question you didn't quite ask- can you say IND OF ZFC
or something else other than YES or NO.
YES you can if you want.
Can I vote that the following are true?
ReplyDelete1. P=NP is independent of ZFC.
2. the fact that 1 is true is independent of ZFC.
3. the fact that 2 is true is independent of ZFC.
...
inf. the fact that 1,2,.. are all true is independent of ZFC.
...
...
Qiqi
If you think P vs NP is ind of ZFC
ReplyDeleteyou still need to say when THAt will be proven, by what kind of math, etc.
Partly stimulated by GASARCH's poll, and partly by a long-standing request from geometer Colin Tan, the question "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?" is now posted on TCS StackExchange (and the question includes a link back to this poll).
ReplyDeleteThis is a warm-up to a series of questions that (as an engineer and medical researcher) I care about very deeply, relating to the fundamental limits to the computational efficiency of verifiable simulations of dynamical and sampling processes.
@Gasarch I think what Qiqi is suggesting is that independence of ZFC is itself independent of ZFC, and that is again independent of ZFC, ad infinitum. So nothing can ever be proven. Is that a legitimate possibility as far as we know?
ReplyDeleteNot directly related to Bill's post, but still. The "madness" of the P vs. NP question makes me kaput.
ReplyDeleteSomething is wrong in all our game. We are exited about ultimate problems (like P vs. NP) without having solved much (much!) "easier" problems. Say, is Floyd-Warshall all-shortest-paths dynamic programming algorithm optimal? Say, where is a Boolean matrix A such that computing y=Ax over GF(2) requires more than n XOR gates? And so on. It seems like we are trying to find/guess a philosophical truth -- "is verifying more powerful than proving?" -- without understanding where the power of algorithms comes from. Is P vs. NP really THE only question of TCS?
I do not know if that is possible.
ReplyDeleteThere is no answer I will DISALLOW;
however, I request only serious answes in that YOU actually believe them.
Say, is Floyd-Warshall all-shortest-paths dynamic programming algorithm optimal?
ReplyDeleteNo, see Fredman SIAM Journal on Computing 1975.
Say, where is a Boolean matrix A such that computing y=Ax over GF(2) requires more than n XOR gates?
In a haystack of random matrices. Why is finding explicit A with this property easier than P versus NP? Is there formal reason for it?
1. No, P != NP.
ReplyDelete2. Not in the next 100 years, definitely not before the singularity (http://en.wikipedia.org/wiki/Technological_singularity).
3. No currently known techniques.
4. The problem will NOT be relevant because of quantum computers. But BQP !contain NP will be shown within 25 years of P!=NP.
5. PhD
1. P != NP
ReplyDelete2. Resolved within ten years
3. Geometric complexity theory and perhaps motivic techniques
4. Of course it will be relevant, just like classical mechanics is still relevant
6. Yes
7. B.Sc in physics :-) from an Australian university
instead of
ReplyDelete- Do you think P=NP or not?
better ask:
what is your subjective
probability for P=NP ?
Noone can be sure (without proof)
so there are doubts.
Whose magnitude is also
interesting.
- Do you think P=NP or not?
just asks whether that subjective
probability is >0.5
Bill: Even if someone believes P vs NP is independent of ZF set theory, shouldn't you also ask them to say whether they believe P!=NP is TRUE (separate from its provability)?
ReplyDeleteStasys: Proving a superlinear lower bound on linear functions is a wonderful, celebrated question (one of my personal favorites), but we don't know a compelling reason why it should be much easier than P vs. NP. The right way to think about P vs. NP is as the historically-chosen "flagship" for HUNDREDS of interrelated questions about the limits of computation, all of which are interesting and almost none of which we know how to answer.
Anon who answered the questions on the blog and Mitchell who answered the questions on the blog.
ReplyDeleteIf you want to be counted email me your answers AND your full names.
already solved
ReplyDeletehttp://rjlipton.wordpress.com/2010/07/01/can-amateurs-solve-pnp/#comment-12187
Scott, I completely agree that P vs. NP is like a "flagship" for the entire lower bounds stuff. (I also use this "flagship" where I can when I must witness the "importance" of lower bounds to "foreigners", e.g. administration.) Like a "flagship" to be seen by other ships (say, that of mathematicians or physicists). My only sorrow we often take this "flagship" for our INTERN use. It does not reflect well enough where we really are. Problems like, how many XOR gates do we need to compute y=Ax, put us on the earth. They also allow us to *granulate* further the problem, until we can finally prove something. Granulations of problems between P and NP are more involved. Also, unlike P vs. NP, such (concrete) problems are already easy to state for any mathematician - a hope they could join our ship. Actually (as you know) Ran Raz already pointed to this "possibility" at
ReplyDeleteBarriers in Computational Complexity Workshop
Also, such (concrete) problems are often just about some modifications of well understood concepts in math. Say, if we consider depth-2 circuits with unbounded fanin XOR gates, then the minimal number of wires in such a circuit for y=Ax is just a "weighted rank" of A over GF(2) = min number R such that A can be written as a product of two matrices containing R ones in total. And here (in depth 2) we can already prove at least n\log n lower bounds. If we require that every XOR computed at the middle layer must be a part (a subset) of at least one output sum, then we can show even n^{3/2} bound. So, if y=Ax question (and the like) would be *really* not easier than P vs. NP, then we could say "we are making some progress" :-)
To Anonymous (4:59 PM, June 20, 2011): Well I meant to show that Floyd-Warshall is optimal is the class of dyn. programming algorithms. More generally, take a particular algorithmic paradigm, formalize it, and prove that some problems cannot be solved better than known paradigm in this class does it. If we stuck, this would be a good motivation to search for a better algorithm, and our failure to prove a lower bound would give a hint on how a better algorithm should work. This line of reaseach is already pushed forward by Borodin, Impagliazzo and their students.
"Why is finding explicit A with this property easier than P versus NP?" If it would be *provably* not easier, we could forgive P-NP and formulate another hypothesis about the hardness of life in the "linear world" where only XOR gates are allowed. Yet another indication that this should be an "easier" problem is that the same problem over Boolean semiring (with OR instead of XOR) is already long solved: explicit matrices require n^{5/2} OR gates.
Sorry, for so lengthy comment.
for taking better advantage of this particular polling channel, questions like the following seem good to include:
ReplyDeletewhat percentage of research time you spent on this issue, in general or in either direction, with or without delivering published or publicly archived results, for the past n years; and what percentage of time you guess you'd likely spend on this for the next n years
Anonymous: There is a trivial sense in which what you suggest must be true. Namely, if ZFC is consistent, then ZFC can't possibly prove "X is independent of ZFC" for any X, since "X is independent of ZFC" trivially implies "ZFC doesn't prove everything," which in turn implies "ZFC is consistent."
ReplyDeleteQ1: P=NP or not?
ReplyDeleteA1: P vs NP will be proved undecidable.
Q2: Resolved when?
A2: 2014 ... by a graduate student! :)
Q3: Resolved how?
A3: Reflecting upon Turing machines in P that verify their own non-verifiability.
Q4: Relevant?
A4: Narrowly no; broadly yes.
Q5: Comments
Q5: This and similar proofs will help build a better-integrated understanding of simulation, sampling, and verifying; this unification will be a central theme of the 21st century STEM enterprise.
Q6: (Scott's question) Given that P!=NP is undecidable in ZF/C, is it nonetheless true?
A6: (Maimonides' answer) "Though the Messiah may tarry, yet do we await him each day" — and for this reason we will regard P!=NP as true ... secure in the knowledge that no formal disproof will ever be given, and the faith that no practical disproof will ever be given.
Suppose $P = NP$ but this is not provable in a theory $T$. Then we could define new complexity classes $P', NP'$ where a language is in $P'$ if there exists a polynomial-time machine $M$ which accepts it AND a $T$-proof that $M$ accepts $L$. Similarly for $NP'$. In this case, $P'$ is not equal to $NP'$. Furthermore, practically all of the complexity results go through as before.
ReplyDeleteFor almost any practical algorithm in $P$, we have a ZFC proof of correctness. SAT remains $NP'$-complete, as proofs of correctness translate through the Cook theorem.
So, in this case, we would still essentially have the same complexity picture as if $P != NP$ is provable in ZFC.
David, your post's argument is very clearly stated (IMHO).
ReplyDeleteHow does the world you describe matches up with Russell Impagliazzo's Five Worlds? Would we need to add another world to Impagliazzo's Five?
@John, suppose $P = NP$ but this is not provable in any plausible set theory (maybe stronger than ZFC).
ReplyDeleteI think this would be more or less analogous to the situation where we have a heuristic algorithm that solves SAT in all practical cases. (The "Heuristica" world). In this case, we would have a heuristic algorithm so effective that, not only does it work nearly always, it works actually always.
In both cases, we get practical solutions for NP problems, but we also get (essentially) the complexity-theoretical separation between P and NP.
And yet, David, your argument applies equally in the opposite direction. Namely, supposing that P!=NP (but unprovably so) then we all live in Impagliazzo's Cryptomania (albeit without proof of citizenship). Such a vexing outcome would perhaps indicate that new borders needed to be negotiated.
ReplyDelete@John: How does that show that we're not in Minicrypt or Pessiland?
ReplyDeleteJohn, why do you believe P?=NP is undecidable? Do you actually have a reason for thinking this?
ReplyDeleteGil Kalai's highly-rated MathOverflow question "What notions are used but not clearly defined in modern mathematics?" is one starting point for developing the notion that P vs NP might be undecidable. Several answerers and commenters pointed out that Gil's question might have been posed in the form:
ReplyDelete-------------
"What intuitions are commonly embraced and/or have proved to be broadly useful, but nonetheless are formally undecidable, in modern mathematics?"
-------------
Meanwhile on TCS StackExchange Emmanuele Viola gave a terrific proof of the question/answer "Are runtime bounds in P decidable? (answer: no)", and it turned out that Juris Hartmanis had proved a broad class of similar results back in the late in his monograph Feasible computations and provable complexity properties (1978).
These various results established that the set P (of languages) is richly endowed with undecidable properties, and so it is natural to conjecture that the separability of P from NP is one of them. After some gestation, this question was posed on TCS StackExchange as "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?" (the question asked includes links back to the preceding questions).
One guiding intuition is that number theorists were led to wonderful theorems when they asked "What properties of the integers are undecidable?", so perhaps the question "What properties of P are undecidable?" might similarly be fruitful.
To the best my (non-expert) knowledge, there is at present no article or textbook that systematically reviews the properties of P and NP that are known or reasonably conjectured to be undecidable, and so any complexity theorist who undertook the (difficult!) task of writing such a review would perform a great service.
Moreover, it is evident that samples and simulations can be viewed as languages to be accepted or rejected by Turing machines that serve as verification processes. Thus the survey perforce would encompass the properties of samples and simulations that are known or reasonably conjectured to be verifiable versus non-verifiable, and this aspect of the survey too would be a considerable and very practical service to practicing engineers (like me).
John: the mathoverflow question was not written by Gil Kalai, it was written by an anonymous user calling himself "Kakaz"
ReplyDeleteThank you anonymous ... the MathOverflow question "What notions are used but not clearly defined in modern mathematics?" is a community wiki question that was posed by "Kakaz" and subsequently edited by Gil Kalai.
ReplyDeleteI've corrected the attribution, and also provided a link to a related (also highly-rated) community wiki on MathOverflow "What are the most attractive Turing undecidable problems in mathematics?"
Should P vs NP prove to be undecidable, it most definitely would head that latter list! :)
It will be interesting which way turns out to be the fastest to solve the P-NP problem:
ReplyDelete1. Our old fashioned, but still most effective, net of mathematical brains fuelled by coffee.
2. A smart special purpose computer which (or should I say who) does the job.
3. Contacting an extraterrestrial intelligence who courteously passes us down the answer.
Maybe, none of the above, but something completely different.
1 - Undecidable
ReplyDelete2 - In more than ten years.
3 - It can't be solved within the framework of set theory but even this can't be proven without an accurate axiomatization of computer science or a computer-oriented enlargement of set theory.
4 - It never was actually. Mathematical problems don't have to be relevant. Conjecturing P<>NP is sufficient for cryptography but a breach in cryptography would be relevant for proving that P=NP.
7 - A Master of algebraic topology from Paris 7.
1)No opinion
ReplyDelete2)No opinion
3)No opinion
4)No opinion
5) Graph Isomorphism is in P. See paper: http://arxiv.org/abs/1004.1808
6) Yes
7) Top Community Mastermind of Intel :)
http://software.intel.com/en-us/articles/blackbelt-hall-of-fame/
-- Michael Trofimov,
Moscow, Russia.
Do you think P=NP or not? You may give other answers as well.
ReplyDeleteP!=NP, NP!=coNP, and PH does not collapse.
When do you think it will be resolved?
June 27, 2012
What kinds of techniques do you think will be used?
Basic computability theory will be used to show that the complement of the bounded halting problem has infinitely often superpolynomial speedup (a stronger statement than P!=NP). The proofs will fit on one page and be intelligible to undergraduates. A clever diagonalization argument will make an end run around the BGS oracle constraint. It will also be shown that there is no fastest algorithm for most familiar computational problems in particular integer and matrix multiplication (as a machine independent statement, these have hard to minimize circuits). It will be shown that the reason these problems in boolean form (BOOLEAN CONVOLUTION and BOOLEAN MM) have gaps between their monotone and nonmonotone circuit complexity (these gaps are known facts) is a closely related property, but that NP-complete problems such as HAMILTONIAN CIRCUIT do not have a gap, and that the latter has easy to minimize circuits (essentially enumerating all possible Hamiltonian circuits).
Will the problem still be relevant given advances in algorithms and in SAT Solvers?
Absolutely. Mathematical research is not a trivial endeavor. Its nontriviality reflects undecidability pushing back at you.
Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem.
The hardness of inverting multiplication (factoring) will be proven using the undecidability of arithmetic with multiplication and the decidability of arithmetic without multiplication (the Presburger arithmetic). Graph Isomorphism will have some form of speedup. Randomized algorithms will be found to have no special advantage against NP-complete problems such as HAMILTON CIRCUIT, but are useful against precisely problems with an undecidable flavor, because randomization skirts the law of the excluded middle (something can be true or false with a probability).
Do I have your permission to print your response? I will do this for some people--- how many depends on how many answer the poll.
Yes
What is your highest degree in and where is it from? This information will be used for statistics only.
D.Phil. Oxford University
1. P=NP
ReplyDelete2. As soon as I have time to create a PoC.
3. Circuit SAT Solver.
4. It is a SAT Solver which will prove P=NP.
5. Factoring will be part of the PoC for the solver. Other problems can infect be put in a different perspective like the 'proven' halting problem, which is in my opinion not undecidable.
6. Yes.
7. MSc Computer Science
will contact you when the PoC is usable
I think that using the model of Turing machines is a good way of proving the P versus NP problem. In my opinion, another strong way of proving this issue, is showing that the language sets P and NP are disjoint. I found an example which do that using both things. I think the probably of been right is very few, however i share it:
ReplyDeletehttp://arxiv.org/abs/1011.2730
(version 11)
PHYSICAL-MATHEMATICIST EDWARD CARL-LUDWIG SIEGEL OF "FUZZYICS"="CATEGORYICS"("SON OF 'TRIZ'")[la jolla; las vegas; seattle; nortonsiegel@gmail.com] FOLLOWING PLATO-ARISTOTLE "SQUARE-OF-OPPOSITION" TRUTH-TABLE MATRIX ANALYTICS AFTER EUCLID AND DEMOSTHENES FORMATIVE GEOMETRY MORPHED INTO HOMOLOGY-COHOMOLOGY PROVED THAT PROVED TRIVIALLY THAT P =/= NP BECAUSE "1" =/= N, I.E. D =/= N VIA MENGER[DIMENSIONTHEORIE, TEUBNER(1929)]-HUREWICZ-WALLMAN[DIMENSION-THEORY, PRINCETON(1941);(1943)] DIMENSION-THEORY AND GAVE THE PROOF AT THE AMERICAN PHYSICAL SOCIETY MARCH MEETINGS[NEW ORLEANS(2009); PORTLAND(2010);DALLAS(2011)].
ReplyDeleteTHIS TRIVIAL PROOF IS A REALIZATION OF LAZLO LOVASZ(MICROSOFT RESEARCH) PREDICTION THAT ALGEBRAIC-TOPOLOGY/ALGEBRAIC-GEOMETRY WOULD SUCCEED!!!
I have read the response of Richard Karp to the P vs NP problem (The P=?NP Poll by William I. Gasarch):
ReplyDelete"My hunch is that the problem will be solved by a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem."
A solution is proposed (the link below, or my P vs NP blog), which is based on the following strategy.
Assume a system/model holds a property, and then find a way to justify this assumption.
The assumption is that there exist no XORs (conflicts) in the model by means of superposition of states, and the justification is by means of the occurrence history of transitions to reach the states. Therefore, the model evolves from some superposition of states to another superposition by means of transition occurrences that are in superposition as well. As a result, the evolution is deterministic, rather than non-deterministic (as in the evolution of individual states).
Consequently, it is more likely that P=NP.
P=/=NP proof is absolutely trivial being only a third of Edward Siegel 1964 proof[AMS Joint Mtg., San Diego(2002)-Abs. # 973-03-128] of Fermat's last-theorem via Menger[Dimensiontheorie, Teubner(1929)] dimension-theory
ReplyDeleteP=/=NP Category-Semantics(C-S) TRIVIAL Proof: EUCLID!!! [(So Miscalled) ``Computational''-``Complexity"(CC) Jargonial-Obfuscation(J-O); (Which???)MillenniumED-ProblemED(M-P): NO CC, "CS" Feet of Clay!!!]
Edward Siegel , London Clay, APS March Meetings 2010-2013
P=/=NP M-P proof is by C-S J-O elimination! C-S P=(?)=NP MEANS (Deterministic).(P-C)=(?)=(NON-D).(P-C)=(NP). C-S P=(?)=NP MEANS (Deterministic). (P-C)=(?)=(Non-D).(P-C) i.e. D.(P)=(?)= N.(P). For inclusion(equality) vs. exclusion(inequality), ir-relevant(P)simply cancels! (Equally any other CC IF both sides identical). Crucial question left(D)=(?)=(N-D), i.e. D =(?)= N. Algorithmics: Deterministic (D) serial vs. Non-deterministic (N) NON-serial, branch fork forms a triangle, its vertices a plane. Menger Dimension-Theory: Dimensionality: D serial is one-dimensional, dim(D) = 1 (definition), versus N non-serial is $>$ one-dimensional, dim(N) = 2(branching; fork; triangle; plane)+ E(probabilistic)$>$ 2 [Sipser [Intro. to Thy. of Comp., PWS Pub. Co.(1997)-p. 49; Fig. 1.15!!!]]. Hence(Euclid[-300 BCE])by simple formative geometry, dim(D) = 1 =/= dim(N) = 2(branching)+ E(probabilistic) $>$ 2, Left-to-Right INclusion VERSUS Right-to-Left EXclusion. Hence P =/= NP!!! QED, i.e. D =/= N, i.e. dim(D) = 1 =/= dim(N) = 2(branching)+ E(probabilistic)$>$ 2 by first millennium BCE, before ``CS'' J-O of CC!!! Harder proofs, but still amenable to FUZZYICS C-S J-O analysis, are any combinations with DIS-similar CCs, especially LHS combining D with low CC and/or RHS combining N with high CC!
DR. EDWARD SIEGEL
CATEGORYSEMANTICS@GMAIL.COM
(206) 659-0235
I am perhaps one of the better known crackpots in NP-completeness.
ReplyDeleteDo you think P=NP or not? You may give other answers as well.
No, I believe Exp=AllQBFs=QBF=SAT. (EXP=QSpace=PSpace=NP).
Generating a k-clause of a sat formula is similar to deciding
an n-k variable qbf, which is strong evidence for NP=Pspace.
Then from above Pspace...
For EXP=PSpace, first have to prove something else.
We have the existence of, for every boolean formula R, a
large monotone boolean formula Q on N variables
that Decides all 2^N qbfs of R. This is called AllQBFs.
Q is roughly the size of the satisfiability tree of R.
That demonstrates a formula and System for deciding
All 2^N QBFs of R that is exponential, which is not a proof,
but is on the road to a proof that decision procedure for
AllQBFs is EXP.
Then, since the formula Q is exponential, deciding and
evaluating a particular qbf of R must examine an exponential
number of clauses of Q. Thats along the road to Exp=PSpace.
When do you think it will be resolved?
Soon. My paper, Introduction to QSpace, at Satisfiability
2002, International Workshop on QBFs, is sure to have a big
impression, after people read it. It shows how to construct
the large monotone formulas Q, and states, without proof,
that QSpace = Exp. I am being humorous, but the paper is
still available from John Franco's repository, or I can send
you a copy. Its old but good.
What kinds of techniques do you think will be used?
Standard. 2^n will be used a lot, just at the Very
Edge of consistent set theory.
Will the problem still be relevant given advances in algorithms
and in SAT Solvers?
Yes. CDCL Sat solvers should try four coloring 200 vertex
ninth degree regular graphs for an exponentially long time.
Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization,
Quantum computers, and/or your own favorite problem.
Quantum computation is hard to believe in. For the value of
TRUTH in my SAT Solver I use 2^16-1, or 16 one bits for a firm Truth value during the billions of intermediate calculations.
I find it hard to place faith in billions of quantums computing
Truth. My longest computation that was satisfiable was a C4D9N172
graph, that took over 115 billion primitive calls and ten days.
I have worked on regular graph coloring and satisfiability for
twentyfive years.
Here are the Golden Points of Regular Graph Coloring,
where N out N instances were satisfiable:
C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72
The C4D9 point is the only tentative point and quite difficult.
Do I have your permission to print your response? I will do this for some people---
how many depends on how many answer the poll.
yes.
What is your highest degree in and where is it from?
This information will be used for statistics only.
My GRE scores were 800V 800M 780A.
I attended Stanford CS PhD program in early 1990s or so, got sucked
into designing the parallel register sets for Intel Pentium multicore chips.
I also chose NP completeness to work on for a long time, and
bugged out of the PhD program.
Sincerely Daniel Pehoushek