tag:blogger.com,1999:blog-3722233.post6456208407222329728..comments2024-10-10T06:29:39.038-05:00Comments on Computational Complexity: Very few problems are in NP intersect coNP but not known to be in P. What to make of that?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-81047016476221303302024-09-10T13:01:24.955-05:002024-09-10T13:01:24.955-05:00What do you think about this recent paper:
https:...What do you think about this recent paper:<br /><br />https://arxiv.org/abs/2401.00747v4<br /><br />which proposes a FPTAS to compute Nash Equilibrium (and hence PPAD=FP)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73298664792404833172024-09-09T15:41:31.525-05:002024-09-09T15:41:31.525-05:00Simple stochastic games are known to be in NP ∩ co...Simple stochastic games are known to be in NP ∩ coNP, but as far as I know, they are not known to be in P. See this paper: https://arxiv.org/abs/2009.10882Peter Shorhttps://www.blogger.com/profile/13823970640202949073noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79327309546979173902024-09-09T13:27:38.637-05:002024-09-09T13:27:38.637-05:00I think the following is type 1. Given a "nic...I think the following is type 1. Given a "nice" unit disk graph (represented as an adjacency list), find the maximum clique (or a clique of size at least a given integer k). The definition of nice is that the graph can be realized with coordinates that are rational numbers of size polynomial in n. The coordinates are a certificate for both YES and NO, as given the coordinates the problem is in P. The nice condition is necessary because some unit disk graphs do not admit a model with polynomial coordinates. I don't know if people guess the problem is in P or not.Guilhermehttps://pageperso.lis-lab.fr/guilherme.fonseca/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22887004818496274852024-09-09T08:15:49.188-05:002024-09-09T08:15:49.188-05:00Do we know or is it obvious whether the "belt...Do we know or is it obvious whether the "beltway problem" of reconstructing the n exits of a beltway around a city, given only the n^2 inter-exit distances, is in co-NP? Similarly the turnpike problem.Markhttps://www.blogger.com/profile/05240495995876752091noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54965449256913590912024-09-09T01:32:17.249-05:002024-09-09T01:32:17.249-05:00My favorite problem in 1) is ARRIVAL: https://link...My favorite problem in 1) is ARRIVAL: https://link.springer.com/chapter/10.1007/978-3-319-44479-6_14.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58403873896768400422024-09-09T01:14:49.512-05:002024-09-09T01:14:49.512-05:00The unknot problem is known to be in NP and in coN...The unknot problem is known to be in NP and in coNP, but is not known to be in P.<br /><br />- Izzy GrosofAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63966443371784785592024-09-08T17:23:25.447-05:002024-09-08T17:23:25.447-05:00Promise problems are in category 3- problems that ...Promise problems are in category 3- problems that have an NP cap coNP feel to them but are not sets so cannot be considered in NP cap coNP. But Good to know there are more in category 3!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45424132327377722072024-09-08T16:51:57.368-05:002024-09-08T16:51:57.368-05:00Do promise problems count? If so, certain lattice ...Do promise problems count? If so, certain lattice problems like GapCVP or GapSVP are also candidates https://cims.nyu.edu/~regev/papers/cvpconp.pdf.Anonymousnoreply@blogger.com