翻訳と辞書
Words near each other
・ NPTC Group
・ NPTN
・ NPTX1
・ NPTX2
・ NPTXR
・ NPU
・ NP (novel)
・ NP Dodge Company
・ NP postcode area
・ NP-40
・ Np-chart
・ NP-completeness
・ NP-easy
・ NP-equivalent
・ NP-hardness
NP-intermediate
・ NP300E5A-A01UB
・ NPA
・ NPA Satellite Mapping
・ NPAC
・ NPAP
・ NPAPI
・ NPAS
・ NPAS1
・ NPAS2
・ NPAS3
・ NPAT
・ NPAT (gene)
・ NPB (disambiguation)
・ NPBL


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

NP-intermediate : ウィキペディア英語版
NP-intermediate

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 Ladner, 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 the other direction is trivial, we can say 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 can not be in NPI. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.
== List of problems that might be NP-intermediate〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237〕 ==

* Factoring integers
* Isomorphism problems: Graph isomorphism problem, Group isomorphism problem, Group automorphism, Ring isomorphism, Ring automorphism
* Computing the rotation distance〔(Rotation distance, triangulations, and hyperbolic geometry )
〕 between two binary trees or the flip distance between two triangulations of the same convex polygon
* The turnpike problem〔(Reconstructing sets from interpoint distances )
〕 of reconstructing points on line from their distance multiset
* Discrete Log Problem and others related to cryptographic assumptions
* Determining winner in parity games〔http://kintali.wordpress.com/2010/06/06/np-intersect-conp/〕
* Determining who has the highest chance of winning a stochastic game〔
* Numbers in boxes problems〔http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html〕
* Agenda control for balanced single-elimination tournaments〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460〕
* Knot triviality〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106〕
* Assuming NEXP is not equal to EXP, padded versions of NEXP-complete problems
* Problems in TFNP〔(On total functions, existence theorems and computational complexity )〕
* Intersecting Monotone SAT〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739〕
* Minimum Circuit Size Problem〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745〕
* Deciding whether a given triangulated 3-manifold is a 3-sphere
* The cutting stock problem with a constant number of object lengths〔http://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827〕
* Monotone self-duality〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950〕
* Planar minimum bisection〔(Approximability of the Minimum Bisection Problem: An Algorithmic Challenge )

* Pigeonhole subset sum〔http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality〕
* Determining the result of a comparison between two sums of square roots of integers〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010〕
* Deciding whether a graph admits a graceful labeling〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384〕
* Gap version of the closest vector in lattice problem〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806〕
* The linear divisibility problem〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331〕
* Finding the VC dimension
* Clustered planarity〔.〕

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「NP-intermediate」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.