Meta tags:

Headings (most frequently used words):

np, intermediate, and, theory, computational, contents, list, of, problems, that, might, be, references, external, links, algebra, number, boolean, logic, geometry, topology, game, graph, algorithms, miscellaneous,

Text of the page (most frequently used words):
the (57), and (34), doi (21), graph (19), problem (16), that (16), #problems (14), edit (13), displaystyle (11), #intermediate (10), complexity (10), isbn (10), with (9), for (9), given (9), wikipedia (8), from (8), time (8), computational (8), theory (8), are (8), npi (7), journal (7), computer (7), 978 (7), 2002 (7), boolean (7), under (6), this (6), science (6), 2021 (6), 540 (6), algorithms (6), page (5), ladner (5), class (5), discrete (5), proceedings (5), 1016 (5), s2cid (5), winner (5), polynomial (5), number (5), acm (5), monotone (5), whether (5), finding (5), which (5), function (5), contents (4), search (4), links (4), springer (4), pdf (4), complete (4), mathematics (4), symposium (4), isomorphism (4), information (4), arxiv (4), games (4), 1145 (4), geometry (4), distance (4), hide (4), move (4), sidebar (4), toggle (3), table (3), view (3), terms (3), january (3), american (3), english (3), retrieved (3), theorem (3), reducibility (3), michael (3), schaefer (3), 2006 (3), lecture (3), notes (3), vol (3), 1007 (3), june (3), powers (3), leaf (3), labeled (3), survey (3), minimum (3), cambridge (3), parity (3), 2007 (3), 107796 (3), usa (3), hyperbolic (3), thomas (3), circuit (3), computing (3), related (3), logic (3), 2020 (3), quasi (3), satisfiability (3), determining (3), vertices (3), same (3), cnf (3), then (3), positive (3), does (3), exist (3), each (3), clause (3), only (3), decision (3), list (3), might (3), tools (3), main (3), languages (2), contact (2), about (2), privacy (2), policy (2), use (2), was (2), all (2), articles (2), 2019 (2), short (2), description (2), wikidata (2), classes (2), foundations (2), structure (2), external (2), 1996 (2), 1006 (2), dimension (2), papadimitriou (2), christos (2), simultaneous (2), fixed (2), edges (2), berlin (2), 32nd (2), international (2), clique (2), width (2), 1137 (2), siam (2), trees (2), joseph (2), dynamic (2), combinatorics (2), labeling (2), bisection (2), eds (2), mathematical (2), 0190 (2), processing (2), letters (2), daniel (2), recent (2), advances (2), university (2), press (2), 1017 (2), 2011 (2), computation (2), stochastic (2), deciding (2), thurston (2), cutting (2), stock (2), constant (2), object (2), lengths (2), 1990 (2), reconstructing (2), sets (2), 339 (2), annual (2), 1990951 (2), rotation (2), triangulations (2), eiter (2), gottlob (2), georg (2), dualization (2), proc (2), sergio (2), artificial (2), symp (2), applications (2), induced (2), subgraph (2), graphs (2), its (2), richard (2), 1975 (2), references (2), testing (2), below (2), miscellaneous (2), recognizing (2), player (2), chooses (2), next (2), step (2), determined (2), vertex (2), game (2), convex (2), between (2), two (2), topology (2), negates (2), there (2), size (2), negative (2), integers (2), have (2), versions (2), logarithm (2), version (2), factoring (2), algebra (2), natural (2), can (2), set (2), disks (2), not (2), exponential (2), hypothesis (2), also (2), assumption (2), neither (2), nor (2), called (2), empty (2), appearance (2), upload (2), file (2), changes (2), history (2), read (2), article (2), log (2), create (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statement, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, text, available, additional, may, apply, using, site, you, agree, registered, trademark, non, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, last, edited, 2026, utc, hidden, categories, written, different, category, https, org, index, php, title, oldid, 1333316117, lance, fortnow, march, 2003, 2013, november, lesson, basic, turing, hardness, zoo, part, 170, 1418886, jcss, 0058, 161, system, sciences, limited, nondeterminism, yannakakis, mihalis, gassner, elisabeth, jünger, percan, merijam, marcus, schulz, embeddings, 4271, 335, archived, original, 2290741, 48381, 11917496_29, 325, theoretic, concepts, workshop, bergen, norway, revised, papers, rotics, udi, 2009, 939, 2519936, 070687256, 909, szeider, stefan, rosamond, frances, fellows, nishimura, ragde, thilikos, 108, jagm, 2001, 1195, gallian, december, 1668059, electronic, karpinski, marek, approximability, algorithmic, challenge, diks, krzysztof, rytter, wojciech, 2420, 44040, 45687, 2_4, 27th, mfcs, warsaw, poland, august, mathon, 1979, note, counting, 132, 0020, 90004, 131, grohe, martin, neuen, 234, 226237505, 009, 03621, 9781009036214, 006, 01366, 187, surveys, condon, anne, 1992, 224, 1147987, 0890, 5401, 90048, 203, jurdziński, marcin, 1998, 124, 1657581, s0020, 00150, 119, cap, geodesics, lyusternik, schnirelmann, 375, 2354878, 521, 71522, cbo9780511735172, 372, geometric, folding, linkages, origami, polyhedra, rourke, demaine, erik, lackenby, marc, paper, 119307517, 4274879, aim, 1604, 00290, 387, efficient, certification, knottedness, norm, jansen, klaus, solis, oba, roberto, opt, algorithm, 753, 2855867, 1287, moor, 1110, 0515, 743, operations, research, skiena, steven, smith, warren, lemke, paul, interpoint, distances, extended, abstract, seidel, raimund, 89791, 362, 98524, 98598, 332, sixth, berkeley, sleator, tarjan, robert, william, 1988, 681, 0928904, jstor, 2307, 647, society, makino, kazuhisa, 2008, 2049, 10096898, 2437000, dam, 017, 2035, 156, applied, aspects, brief, kabanets, valentine, cai, jin, 2000, minimization, portland, oregon, tr99, 045, eccc, 785205, 58113, 184, 335305, 335314, hypergraph, transversal, flesca, greco, leone, nicola, ianni, giovambattista, 2424, 564, 44190, 45757, 7_53, 549, logics, intelligence, european, conference, jelia, cosenza, italy, september, 1994, addison, wesley, 236, 9780201530827, adleman, leonard, manders, kenneth, 1977, randomness, intractibility, 800105, 803405, 9th, stoc, lincoln, andrea, 2023, 7155, jgaa, 00625, 2306, 11185, 329, quasipolynomiality, smallest, missing, williams, virginia, vassilevska, eppstein, david, kisfaludi, bak, sándor, intersection, 1638, 61197, 599, 9781611975994, 100, 1812, 03960, 1621, 31st, soda, salt, lake, city, chawla, shuchi, 1978, 226, 0521057, 216, 10th, ann, grädel, erich, kolaitis, phokion, libkin, leonid, marx, maarten, venema, yde, weinstein, scott, texts, theoretical, eatcs, series, 348, 1133, 03001, zbl, 00428, verlag, finite, model, vardi, moshe, spencer, joel, 171, 14352974, 321864, 321877, 155, family, bound, vapnik, chervonenkis, existence, embedding, bounded, admits, graceful, planar, automorphisms, automorphism, group, chosen, randomly, reaching, designated, sink, highest, priority, reached, polyhedron, simple, closed, quasigeodesic, knot, triviality, turnpike, points, line, their, multiset, flip, polygon, threshold, binary, self, duality, formula, invariant, transformation, variables, output, value, dnf, formulas, functions, they, represent, truth, integer, most, imsat, intersecting, containing, having, variable, common, conjunctive, normal, form, linear, divisibility, divisor, congruent, modulo, others, cryptographic, assumptions, input, factor, interval, require, solved, including, large, disjoint, few, implies, these, must, plane, unit, explicitly, constructs, although, otherwise, uninteresting, open, question, any, has, property, provides, conditions, constrained, cannot, some, considered, good, candidates, being, dichotomy, but, such, shown, result, asserting, contains, since, true, follows, free, encyclopedia, item, other, projects, printable, download, print, export, switch, legacy, parser, get, shortened, url, cite, permanent, link, what, here, general, actions, talk, português, polski, italiano, עברית, français, subsection, top, personal, special, pages, community, portal, learn, help, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
np intermediate wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 list of problems that might be np intermediate toggle list of problems that might be np intermediate subsection 1 1 algebra and number theory 1 2 boolean logic 1 3 computational geometry and computational topology 1 4 game theory 1 5 graph algorithms 1 6 miscellaneous 2 references 3 external links toggle the table of contents np intermediate 5 languages français עברית italiano polski português edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia complexity class of problems in computational complexity problems that are in the complexity class np but are neither in the class p nor np complete are called np intermediate and the class of such problems is called npi ladner s theorem shown in 1975 by richard e ladner 1 is a result asserting that if p np then npi is not empty that is np contains problems that are neither in p nor np complete since it is also true that if npi problems exist then p np it follows that p np if and only if npi is empty under the assumption that p np ladner explicitly constructs a problem in npi although this problem is artificial and otherwise uninteresting it is an open question whether any natural problem has the same property schaefer s dichotomy theorem provides conditions under which classes of constrained boolean satisfiability problems cannot be in npi 2 3 some problems that are considered good candidates for being np intermediate are the graph isomorphism problem and decision versions of factoring and the discrete logarithm under the exponential time hypothesis there exist natural problems that require quasi polynomial time and can be solved in that time including finding a large disjoint set of unit disks from a given set of disks in the hyperbolic plane 4 and finding a graph with few vertices that is not an induced subgraph of a given graph 5 the exponential time hypothesis also implies that no quasi polynomial time problem can be np complete so under this assumption these problems must be np intermediate list of problems that might be np intermediate edit algebra and number theory edit a decision version of factoring integers for input n displaystyle n and k displaystyle k does n displaystyle n have a factor in the interval 2 k displaystyle 2 k decision versions of the discrete logarithm problem and others related to cryptographic assumptions linear divisibility given integers x displaystyle x and y displaystyle y does y displaystyle y have a divisor congruent to 1 modulo x displaystyle x 6 7 boolean logic edit imsat the boolean satisfiability problem for intersecting monotone cnf conjunctive normal form with each clause containing only positive or only negative terms and each positive clause having a variable in common with each negative clause 8 minimum circuit size problem given the truth table of a boolean function and positive integer s displaystyle s does there exist a circuit of size at most s displaystyle s for this function 9 monotone dualization given cnf and dnf formulas for monotone boolean functions do they represent the same function 10 monotone self duality given a cnf formula for a boolean function is the function invariant under a transformation that negates all of its variables and then negates the output value 10 computational geometry and computational topology edit determining whether the rotation distance 11 between two binary trees or the flip distance between two triangulations of the same convex polygon is below a given threshold the turnpike problem of reconstructing points on line from their distance multiset 12 the cutting stock problem with a constant number of object lengths 13 knot triviality 14 finding a simple closed quasigeodesic on a convex polyhedron 15 game theory edit determining the winner in parity games in which graph vertices are labeled by which player chooses the next step and the winner is determined by the parity of the highest priority vertex reached 16 determining the winner for stochastic graph games in which graph vertices are labeled by which player chooses the next step or whether it is chosen randomly and the winner is determined by reaching a designated sink vertex 17 graph algorithms edit graph isomorphism problem 18 finding a graph s automorphism group 19 finding the number of graph automorphisms 19 planar minimum bisection 20 deciding whether a graph admits a graceful labeling 21 recognizing leaf powers and k leaf powers 22 recognizing graphs of bounded clique width 23 testing the existence of a simultaneous embedding with fixed edges 24 miscellaneous edit testing whether the vapnik chervonenkis dimension of a given family of sets is below a given bound 25 references edit ladner richard 1975 on the structure of polynomial time reducibility journal of the acm 22 1 155 171 doi 10 1145 321864 321877 s2cid 14352974 grädel erich kolaitis phokion g libkin leonid marx maarten spencer joel vardi moshe y venema yde weinstein scott 2007 finite model theory and its applications texts in theoretical computer science an eatcs series berlin springer verlag p 348 isbn 978 3 540 00428 8 zbl 1133 03001 schaefer thomas j 1978 the complexity of satisfiability problems pdf proc 10th ann acm symp on theory of computing pp 216 226 mr 0521057 kisfaludi bak sándor 2020 hyperbolic intersection graphs and quasi polynomial time in chawla shuchi ed proceedings of the 31st annual acm siam symposium on discrete algorithms soda 2020 salt lake city ut usa january 5 8 2020 pp 1621 1638 arxiv 1812 03960 doi 10 1137 1 9781611975994 100 isbn 978 1 61197 599 4 eppstein david lincoln andrea williams virginia vassilevska 2023 quasipolynomiality of the smallest missing induced subgraph journal of graph algorithms and applications 27 5 329 339 arxiv 2306 11185 doi 10 7155 jgaa 00625 adleman leonard manders kenneth 1977 reducibility randomness and intractibility proceedings of the 9th acm symp on theory of computing stoc 77 doi 10 1145 800105 803405 papadimitriou christos h 1994 computational complexity addison wesley p 236 isbn 9780201530827 eiter thomas gottlob georg 2002 hypergraph transversal computation and related problems in logic and ai in flesca sergio greco sergio leone nicola ianni giovambattista eds logics in artificial intelligence european conference jelia 2002 cosenza italy september 23 26 proceedings lecture notes in computer science vol 2424 springer pp 549 564 doi 10 1007 3 540 45757 7_53 isbn 978 3 540 44190 8 kabanets valentine cai jin yi 2000 circuit minimization problem proc 32nd symposium on theory of computing portland oregon usa pp 73 79 doi 10 1145 335305 335314 isbn 1 58113 184 4 s2cid 785205 eccc tr99 045 1 2 eiter thomas makino kazuhisa gottlob georg 2008 computational aspects of monotone dualization a brief survey discrete applied mathematics 156 11 2035 2049 doi 10 1016 j dam 2007 04 017 mr 2437000 s2cid 10096898 sleator daniel d tarjan robert e thurston william p 1988 rotation distance triangulations and hyperbolic geometry journal of the american mathematical society 1 3 647 681 doi 10 2307 1990951 jstor 1990951 mr 0928904 skiena steven smith warren d lemke paul 1990 reconstructing sets from interpoint distances extended abstract in seidel raimund ed proceedings of the sixth annual symposium on computational geometry berkeley ca usa june 6 8 1990 acm pp 332 339 doi 10 1145 98524 98598 isbn 0 89791 362 0 jansen klaus solis oba roberto 2011 a polynomial time opt 1 algorithm for the cutting stock problem with a constant number of object lengths mathematics of operations research 36 4 743 753 doi 10 1287 moor 1110 0515 mr 2855867 lackenby marc 2021 the efficient certification of knottedness and thurston norm advances in mathematics 387 107796 paper no 107796 arxiv 1604 00290 doi 10 1016 j aim 2021 107796 mr 4274879 s2cid 119307517 demaine erik d o rourke joseph 2007 24 geodesics lyusternik schnirelmann geometric folding algorithms linkages origami polyhedra cambridge cambridge university press pp 372 375 doi 10 1017 cbo9780511735172 isbn 978 0 521 71522 5 mr 2354878 jurdziński marcin 1998 deciding the winner in parity games is in up displaystyle cap co up information processing letters 68 3 119 124 doi 10 1016 s0020 0190 98 00150 1 mr 1657581 condon anne 1992 the complexity of stochastic games information and computation 96 2 203 224 doi 10 1016 0890 5401 92 90048 k mr 1147987 grohe martin neuen daniel june 2021 recent advances on the graph isomorphism problem surveys in combinatorics 2021 cambridge university press pp 187 234 arxiv 2011 01366 doi 10 1017 9781009036214 006 isbn 978 1 009 03621 4 s2cid 226237505 1 2 mathon r 1979 a note on the graph isomorphism counting problem information processing letters 8 3 131 132 doi 10 1016 0020 0190 79 90004 8 karpinski marek 2002 approximability of the minimum bisection problem an algorithmic challenge in diks krzysztof rytter wojciech eds mathematical foundations of computer science 2002 27th international symposium mfcs 2002 warsaw poland august 26 30 2002 proceedings lecture notes in computer science vol 2420 springer pp 59 67 doi 10 1007 3 540 45687 2_4 isbn 978 3 540 44040 6 gallian joseph a december 17 2021 a dynamic survey of graph labeling electronic journal of combinatorics 5 dynamic survey 6 mr 1668059 nishimura n ragde p thilikos d m 2002 on graph powers for leaf labeled trees journal of algorithms 42 69 108 doi 10 1006 jagm 2001 1195 fellows michael r rosamond frances a rotics udi szeider stefan 2009 clique width is np complete siam journal on discrete mathematics 23 2 909 939 doi 10 1137 070687256 mr 2519936 gassner elisabeth jünger michael percan merijam schaefer marcus schulz michael 2006 simultaneous graph embeddings with fixed edges graph theoretic concepts in computer science 32nd international workshop wg 2006 bergen norway june 22 24 2006 revised papers pdf lecture notes in computer science vol 4271 berlin springer pp 325 335 doi 10 1007 11917496_29 isbn 978 3 540 48381 6 mr 2290741 archived from the original pdf on 2021 10 22 retrieved 2019 09 10 papadimitriou christos h yannakakis mihalis 1996 on limited nondeterminism and the complexity of the v c dimension journal of computer and system sciences 53 2 part 1 161 170 doi 10 1006 jcss 1996 0058 mr 1418886 external links edit complexity zoo class npi basic structure turing reducibility and np hardness lance fortnow 24 march 2003 foundations of complexity lesson 16 ladner s theorem retrieved 1 november 2013 retrieved from https en wikipedia org w index php title np intermediate oldid 1333316117 category complexity classes hidden categories articles with short description short description is different from wikidata use american english from january 2019 all wikipedia articles written in american english this page was last edited on 17 january 2026 at 00 46 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents np intermediate 5 languages add topic