tag:blogger.com,1999:blog-3722233.post5334459752981812402..comments2021-03-01T15:31:15.631-06:00Comments on Computational Complexity: I am conducting a NEW POLL on P vs NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger41125tag:blogger.com,1999:blog-3722233.post-60598713452901525652020-08-18T13:29:54.965-05:002020-08-18T13:29:54.965-05:00i hope so, a guess was submitted yesterday and the...i hope so, a guess was submitted yesterday and theres a lot of buzz<br />-anonanonhttps://www.blogger.com/profile/03387037541439137893noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51160858727637593152020-08-18T13:29:31.541-05:002020-08-18T13:29:31.541-05:00i hope so, a non cs solved it yesterdayi hope so, a non cs solved it yesterdayanonhttps://www.blogger.com/profile/03387037541439137893noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12826587102565671172017-02-09T12:22:26.154-06:002017-02-09T12:22:26.154-06:00I am perhaps one of the better known crackpots in ...I am perhaps one of the better known crackpots in NP-completeness.<br /><br />Do you think P=NP or not? You may give other answers as well.<br /><br />No, I believe Exp=AllQBFs=QBF=SAT. (EXP=QSpace=PSpace=NP).<br /><br />Generating a k-clause of a sat formula is similar to deciding <br />an n-k variable qbf, which is strong evidence for NP=Pspace. <br />Then from above Pspace...<br /><br />For EXP=PSpace, first have to prove something else. <br />We have the existence of, for every boolean formula R, a <br />large monotone boolean formula Q on N variables <br />that Decides all 2^N qbfs of R. This is called AllQBFs.<br /><br />Q is roughly the size of the satisfiability tree of R. <br />That demonstrates a formula and System for deciding <br />All 2^N QBFs of R that is exponential, which is not a proof, <br />but is on the road to a proof that decision procedure for <br />AllQBFs is EXP. <br /><br />Then, since the formula Q is exponential, deciding and <br />evaluating a particular qbf of R must examine an exponential <br />number of clauses of Q. Thats along the road to Exp=PSpace.<br /><br />When do you think it will be resolved?<br /><br />Soon. My paper, Introduction to QSpace, at Satisfiability <br />2002, International Workshop on QBFs, is sure to have a big <br />impression, after people read it. It shows how to construct <br />the large monotone formulas Q, and states, without proof,<br />that QSpace = Exp. I am being humorous, but the paper is <br />still available from John Franco's repository, or I can send <br />you a copy. Its old but good.<br /><br />What kinds of techniques do you think will be used?<br /><br />Standard. 2^n will be used a lot, just at the Very <br />Edge of consistent set theory. <br /><br />Will the problem still be relevant given advances in algorithms <br />and in SAT Solvers?<br /><br />Yes. CDCL Sat solvers should try four coloring 200 vertex <br />ninth degree regular graphs for an exponentially long time.<br /><br />Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, <br />Quantum computers, and/or your own favorite problem.<br /><br />Quantum computation is hard to believe in. For the value of <br />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. <br />I find it hard to place faith in billions of quantums computing <br />Truth. My longest computation that was satisfiable was a C4D9N172 <br />graph, that took over 115 billion primitive calls and ten days. <br />I have worked on regular graph coloring and satisfiability for <br />twentyfive years. <br /><br />Here are the Golden Points of Regular Graph Coloring, <br />where N out N instances were satisfiable:<br /><br />C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72 <br />The C4D9 point is the only tentative point and quite difficult. <br /><br />Do I have your permission to print your response? I will do this for some people--- <br />how many depends on how many answer the poll.<br />yes.<br /><br />What is your highest degree in and where is it from? <br />This information will be used for statistics only.<br /><br />My GRE scores were 800V 800M 780A. <br />I attended Stanford CS PhD program in early 1990s or so, got sucked <br />into designing the parallel register sets for Intel Pentium multicore chips.<br />I also chose NP completeness to work on for a long time, and <br />bugged out of the PhD program.<br />Sincerely Daniel PehoushekAnonymoushttps://www.blogger.com/profile/03196523522611757037noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1242893467145005302013-10-31T14:09:01.920-05:002013-10-31T14:09:01.920-05:00P=/=NP proof is absolutely trivial being only a th...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<br /><br />P=/=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!!!]<br /><br />Edward Siegel , London Clay, APS March Meetings 2010-2013<br /><br />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! <br /><br />DR. EDWARD SIEGEL<br />CATEGORYSEMANTICS@GMAIL.COM<br />(206) 659-0235Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27208101270336535612012-08-24T09:11:18.654-05:002012-08-24T09:11:18.654-05:00I have read the response of Richard Karp to the P ...I have read the response of Richard Karp to the P vs NP problem (The P=?NP Poll by William I. Gasarch):<br /><br />"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."<br /><br />A solution is proposed (the link below, or my P vs NP blog), which is based on the following strategy.<br /><br />Assume a system/model holds a property, and then find a way to justify this assumption.<br /><br />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).<br /><br />Consequently, it is more likely that P=NP.Anonymoushttps://www.blogger.com/profile/02357298008085577660noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59255060349831309822011-11-28T12:18:13.217-06:002011-11-28T12:18:13.217-06:00PHYSICAL-MATHEMATICIST EDWARD CARL-LUDWIG SIEGEL O...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)].<br />THIS TRIVIAL PROOF IS A REALIZATION OF LAZLO LOVASZ(MICROSOFT RESEARCH) PREDICTION THAT ALGEBRAIC-TOPOLOGY/ALGEBRAIC-GEOMETRY WOULD SUCCEED!!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3291815719438270942011-07-19T09:38:56.469-05:002011-07-19T09:38:56.469-05:00I think that using the model of Turing machines is...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:<br />http://arxiv.org/abs/1011.2730<br />(version 11)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62472417835027915822011-07-12T04:15:54.758-05:002011-07-12T04:15:54.758-05:001. P=NP
2. As soon as I have time to create a P...1. P=NP<br /> 2. As soon as I have time to create a PoC.<br /> 3. Circuit SAT Solver.<br /> 4. It is a SAT Solver which will prove P=NP.<br /> 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.<br /> 6. Yes.<br /> 7. MSc Computer Science<br /><br />will contact you when the PoC is usableAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70119672739374542642011-06-27T12:36:50.219-05:002011-06-27T12:36:50.219-05:00Do you think P=NP or not? You may give other answe...Do you think P=NP or not? You may give other answers as well. <br /><br />P!=NP, NP!=coNP, and PH does not collapse. <br /><br />When do you think it will be resolved? <br /><br />June 27, 2012<br /><br />What kinds of techniques do you think will be used? <br /><br />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).<br /><br />Will the problem still be relevant given advances in algorithms and in SAT Solvers? <br /><br />Absolutely. Mathematical research is not a trivial endeavor. Its nontriviality reflects undecidability pushing back at you.<br /><br />Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem. <br /><br />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).<br /><br />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. <br /><br />Yes<br /><br />What is your highest degree in and where is it from? This information will be used for statistics only.<br /><br />D.Phil. Oxford UniversityAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82763497113352678272011-06-25T12:45:09.702-05:002011-06-25T12:45:09.702-05:001)No opinion
2)No opinion
3)No opinion
4)No opinio...1)No opinion<br />2)No opinion<br />3)No opinion<br />4)No opinion<br />5) Graph Isomorphism is in P. See paper: http://arxiv.org/abs/1004.1808 <br />6) Yes<br />7) Top Community Mastermind of Intel :)<br />http://software.intel.com/en-us/articles/blackbelt-hall-of-fame/<br />-- Michael Trofimov,<br />Moscow, Russia.MT2https://www.blogger.com/profile/03601325337054828213noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47908224590773768412011-06-24T16:59:17.601-05:002011-06-24T16:59:17.601-05:001 - Undecidable
2 - In more than ten years.
3 - ...1 - Undecidable<br /><br />2 - In more than ten years.<br /><br />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.<br /><br />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.<br /><br />7 - A Master of algebraic topology from Paris 7.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79276610656768696392011-06-23T22:24:42.338-05:002011-06-23T22:24:42.338-05:00It will be interesting which way turns out to be t...It will be interesting which way turns out to be the fastest to solve the P-NP problem:<br /><br />1. Our old fashioned, but still most effective, net of mathematical brains fuelled by coffee.<br /><br />2. A smart special purpose computer which (or should I say who) does the job.<br /><br />3. Contacting an extraterrestrial intelligence who courteously passes us down the answer.<br /><br />Maybe, none of the above, but something completely different.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61949819652921736742011-06-23T09:24:48.136-05:002011-06-23T09:24:48.136-05:00Thank you anonymous ... the MathOverflow question ...Thank you anonymous ... the <i>MathOverflow</i> 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. <br /><br />I've corrected the attribution, and also provided a link to a related (also highly-rated) community wiki on <i>MathOverflow</i> "What are the most attractive Turing undecidable problems in mathematics?" <br /><br />Should P vs NP prove to be undecidable, it most definitely would head that latter list! :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82768903049701985602011-06-23T08:50:47.454-05:002011-06-23T08:50:47.454-05:00John: the mathoverflow question was not written by...John: the mathoverflow question was not written by Gil Kalai, it was written by an anonymous user calling himself "Kakaz"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23301059387754054762011-06-23T06:13:23.100-05:002011-06-23T06:13:23.100-05:00Gil Kalai's highly-rated MathOverflow question...Gil Kalai's highly-rated <i>MathOverflow</i> 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:<br /><br />-------------<br />"What intuitions are commonly embraced and/or have proved to be broadly useful, but nonetheless are formally undecidable, in modern mathematics?"<br />-------------<br /><br />Meanwhile on <i>TCS StackExchange</i> 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 <i>Feasible computations and provable complexity properties</i> (1978).<br /><br />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 <a href="http://cstheory.stackexchange.com/questions/7059/do-the-undecidable-attributes-of-p-pose-an-obstruction-to-deciding-p-versus-np" rel="nofollow">links</a> back to the preceding questions).<br /><br />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. <br /><br />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. <br /><br />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 Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78340002122252469622011-06-23T04:59:37.406-05:002011-06-23T04:59:37.406-05:00John, why do you believe P?=NP is undecidable? Do ...John, why do you believe P?=NP is undecidable? Do you actually have a reason for thinking this?Mitchellhttps://www.blogger.com/profile/10768655514143252049noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91385946749040166262011-06-22T23:17:35.799-05:002011-06-22T23:17:35.799-05:00@John: How does that show that we're not in Mi...@John: How does that show that we're not in Minicrypt or Pessiland?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40794612955952062192011-06-22T20:40:50.353-05:002011-06-22T20:40:50.353-05:00And yet, David, your argument applies equally in t...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.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63753055951336787362011-06-22T08:56:51.949-05:002011-06-22T08:56:51.949-05:00@John, suppose $P = NP$ but this is not provable i...@John, suppose $P = NP$ but this is not provable in any plausible set theory (maybe stronger than ZFC).<br /><br />I 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.<br /><br />In both cases, we get practical solutions for NP problems, but we also get (essentially) the complexity-theoretical separation between P and NP.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27087461188759468202011-06-22T08:40:09.998-05:002011-06-22T08:40:09.998-05:00David, your post's argument is very clearly st...David, your post's argument is very clearly stated (IMHO). <br /><br />How does the world you describe matches up with <a href="http://blog.computationalcomplexity.org/2011/06/update-on-impagliazzos-worlds.html" rel="nofollow">Russell Impagliazzo's Five Worlds</a>? Would we need to add another world to Impagliazzo's Five?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55357566588506274722011-06-22T07:54:42.425-05:002011-06-22T07:54:42.425-05:00Suppose $P = NP$ but this is not provable in a the...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. <br /><br />For 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.<br /><br />So, in this case, we would still essentially have the same complexity picture as if $P != NP$ is provable in ZFC.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19483821369519212582011-06-21T18:10:31.755-05:002011-06-21T18:10:31.755-05:00Q1: P=NP or not?
A1: P vs NP will be proved undec...<b>Q1:</b> P=NP or not? <br /><b>A1:</b> P vs NP will be proved undecidable.<br /><br /><b>Q2:</b> Resolved when?<br /><b>A2:</b> 2014 ... by a graduate student! :)<br /><br /><b>Q3:</b> Resolved how?<br /><b>A3:</b> Reflecting upon Turing machines in P that verify their own non-verifiability.<br /><br /><b>Q4:</b> Relevant?<br /><b>A4:</b> Narrowly no; broadly yes.<br /><br /><b>Q5:</b> Comments<br /><b>Q5:</b> 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.<br /><br /><b>Q6:</b> (Scott's question) Given that P!=NP is undecidable in ZF/C, is it nonetheless true? <br /><b>A6:</b> (Maimonides' answer) "<a href="http://dabacon.org/pontiff/?p=4979#comment-536745" rel="nofollow">Though the Messiah may tarry, yet do we await him each day</a>" — 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.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64574017653075109942011-06-21T17:56:25.278-05:002011-06-21T17:56:25.278-05:00Anonymous: There is a trivial sense in which what ...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."Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25919381315364797352011-06-21T14:42:59.022-05:002011-06-21T14:42:59.022-05:00for taking better advantage of this particular pol...for taking better advantage of this particular polling channel, questions like the following seem good to include:<br /><br />what 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 yearscomputationalisthttps://www.blogger.com/profile/13876886980860698327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46607571842246099652011-06-21T11:23:23.860-05:002011-06-21T11:23:23.860-05:00Scott, I completely agree that P vs. NP is like a ...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<br /><br /><a href="http://intractability.princeton.edu/blog/2009/06/program-for-barriers-in-computational-complexity-workshop/" rel="nofollow">Barriers in Computational Complexity Workshop</a> <br /><br />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" :-)<br /><br />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.<br /><br />"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. <br /><br />Sorry, for so lengthy comment.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.com