tag:blogger.com,1999:blog-3722233.post2536467445996425170..comments2023-06-10T02:59:19.319-05:00Comments on Computational Complexity: Inverting Onto FunctionsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-49051982425614226032018-12-29T15:57:04.652-06:002018-12-29T15:57:04.652-06:00You can review it in
https://www.reddit.com/r/Pvs...You can review it in<br /><br />https://www.reddit.com/r/PvsNPsolutions/comments/aapc51/review_request_succinctmaximum_promise_problem/<br /><br />Thanks in advance...Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60565321859625307632018-12-27T14:10:59.626-06:002018-12-27T14:10:59.626-06:00You can participate in the debate
https://www.red...You can participate in the debate<br /><br />https://www.reddit.com/r/compsci/comments/a9l018/is_this_complexity_theory_proof_correct<br /><br />ThanksFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39724016412691002922018-12-25T21:10:42.704-06:002018-12-25T21:10:42.704-06:00P versus NP is considered as one of the most impor...P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Given a positive integer x and a collection S of positive integers, MAXIMUM is the problem of deciding whether x is the maximum of S. We prove this problem is complete for P. Another problem is SUCCINCT-MAXIMUM. SUCCINCT-MAXIMUM contains the instances of MAXIMUM that can be represented by an exponentially more succinct way. We show this succinct version of MAXIMUM must not be in P. Under the assumption of P = NP, we prove the membership of SUCCINCT-MAXIMUM in P is also hold. In this way, we demonstrate the complexity class P is not equal to NP by the reduction ad absurdum rule. Another major complexity classes are LOGSPACE and NLOGSPACE. Whether LOGSPACE = NLOGSPACE is another fundamental question that it is as important as it is unresolved. We show the problem MAXIMUM can be solved in logarithmic space. Consequently, we demonstrate the complexity class LOGSPACE is equal to P and thus, LOGSPACE is equal to NLOGSPACE.<br /><br />https://www.academia.edu/38039040/LOGSPACE_vs_NLOGSPACE_and_P_vs_NPFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12284665275994813142018-12-22T10:21:56.116-06:002018-12-22T10:21:56.116-06:00You are right. Now fixed. Thanks.You are right. Now fixed. Thanks.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61473800056991091832018-12-17T07:25:40.528-06:002018-12-17T07:25:40.528-06:00Minor point: in the second bullet point of the des...Minor point: in the second bullet point of the description of Q', there is "more precisely for all x there is a y such that g(y) = g(x)", but should be "[...]g(y) = x", correct?Konrad Voelkelhttps://www.blogger.com/profile/16506527691093198845noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56652117974299741512018-12-14T06:26:17.802-06:002018-12-14T06:26:17.802-06:00Good point. I meant any polynomial-time computable...Good point. I meant any polynomial-time computable function with a single bit output.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46157776174858661632018-12-14T03:29:50.777-06:002018-12-14T03:29:50.777-06:00I found it strange that any polynomial time comput...I found it strange that any polynomial time computable function of the witness works to characterize the Q', because we can use the identity function which gives the witness and this implies that Q' is equivalent to Q.Anonymoushttps://www.blogger.com/profile/11949441880455865523noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60029009096971424902018-12-13T16:23:26.282-06:002018-12-13T16:23:26.282-06:00You don't have to focus on the first bit. You ...You don't have to focus on the first bit. You get the same Q' if you use any other bit, or any polynomial-time time computable function of the witness. Q' implies that P = NP intersect co-NP so you already get factoring and discrete log as a consequence.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37443149353278362882018-12-13T14:38:19.883-06:002018-12-13T14:38:19.883-06:00I see that Q is interesting, I am not sure why Q&#...I see that Q is interesting, I am not sure why Q' is of interest? Is this related to a known result that states computing the first/last bit of inverse of Discrete Log is as hard as inverting Discrete Log?<br /><br />Thanks<br />Anonymousnoreply@blogger.com