Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Weakly_NP-complete> ?p ?o }
Showing triples 1 to 37 of
37
with 100 triples per page.
- Weakly_NP-complete abstract "In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard), if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial. For example, the NP-hard knapsack problem can be solved by a dynamic programming algorithm requiring a number of steps polynomial in the size of the knapsack and the number of items (assuming that all data are scaled to be integers); however, the runtime of this algorithm is exponential time since the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and Johnson (1979) observed, “A pseudo-polynomial-time algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.” The related term strongly NP-complete (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in unary (that is, if the data are “small” relative to the overall input size).".
- Weakly_NP-complete wikiPageExternalLink complexi.htm.
- Weakly_NP-complete wikiPageID "8047019".
- Weakly_NP-complete wikiPageLength "1934".
- Weakly_NP-complete wikiPageOutDegree "12".
- Weakly_NP-complete wikiPageRevisionID "664148974".
- Weakly_NP-complete wikiPageWikiLink Analysis_of_algorithms.
- Weakly_NP-complete wikiPageWikiLink Category:Complexity_classes.
- Weakly_NP-complete wikiPageWikiLink Category:Computational_complexity_theory.
- Weakly_NP-complete wikiPageWikiLink Category:Weakly_NP-complete_problems.
- Weakly_NP-complete wikiPageWikiLink Dynamic_programming.
- Weakly_NP-complete wikiPageWikiLink Exponential_time.
- Weakly_NP-complete wikiPageWikiLink Knapsack_problem.
- Weakly_NP-complete wikiPageWikiLink NP-complete.
- Weakly_NP-complete wikiPageWikiLink NP-completeness.
- Weakly_NP-complete wikiPageWikiLink NP-hard.
- Weakly_NP-complete wikiPageWikiLink NP-hardness.
- Weakly_NP-complete wikiPageWikiLink Pseudo-polynomial_time.
- Weakly_NP-complete wikiPageWikiLink Strongly_NP-complete.
- Weakly_NP-complete wikiPageWikiLink Time_complexity.
- Weakly_NP-complete wikiPageWikiLink Unary_numeral_system.
- Weakly_NP-complete wikiPageWikiLinkText "Weakly NP-complete".
- Weakly_NP-complete wikiPageWikiLinkText "weakly NP-complete".
- Weakly_NP-complete hasPhotoCollection Weakly_NP-complete.
- Weakly_NP-complete subject Category:Complexity_classes.
- Weakly_NP-complete subject Category:Computational_complexity_theory.
- Weakly_NP-complete subject Category:Weakly_NP-complete_problems.
- Weakly_NP-complete hypernym Algorithm.
- Weakly_NP-complete type Software.
- Weakly_NP-complete type Class.
- Weakly_NP-complete comment "In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard), if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial.".
- Weakly_NP-complete label "Weakly NP-complete".
- Weakly_NP-complete sameAs m.026pnb_.
- Weakly_NP-complete sameAs Q7977975.
- Weakly_NP-complete sameAs Q7977975.
- Weakly_NP-complete wasDerivedFrom Weakly_NP-complete?oldid=664148974.
- Weakly_NP-complete isPrimaryTopicOf Weakly_NP-complete.