This HTML5 document contains 73 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n9https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Online_fair_division
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Strong_NP-completeness
rdf:type
yago:Attribute100024264 dbo:Building yago:Class107997703 yago:State100024720 yago:Group100031264 yago:Condition113920835 yago:Problem114410605 yago:Abstraction100002137 yago:WikicatComplexityClasses yago:WikicatStronglyNP-completeProblems yago:Difficulty114408086 yago:Collection107951464
rdfs:label
Fortemente NP-completo Totalmente NP-completo Problem silnie NP-zupełny Strong NP-completeness
rdfs:comment
In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing problem is a list of objects of specific sizes and a size for the bins that must contain the objects—these object sizes and bin size are numerical parameters. Some strongly NP-complete problems may still be easy to solve on average, but it's more likely that difficult instances will be encountered in practice. Problem silnie NP-zupełny (ang. Strongly NP-Complete) to taki problem decyzyjny, który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje NP-zupełny. Istnienie algorytmu pseudowielomianowego dla dowolnego problemu silnie NP-zupełnego implikowałoby równość P=NP, a więc jest uważane za wysoce nieprawdopodobne. Natomiast problemy silnie NP-zupełne pozostałyby NP-zupełne nawet przy kodowaniu unarnym, stąd też są również znane jako problemy jedynkowo NP-zupełne. Em Complexidade computacional, NP-completude forte é uma propriedade computacional de problemas que é um caso especial de NP-completude. Um problema computacional geral pode ter parâmetros numéricos. Por exemplo, a entrada para o problema de empacotamento de caixas é uma lista de objetos de tamanhos específicos e um tamanho para a caixa que deve conter os objetos — estes tamanhos de objetos e tamanhos de caixas são parâmetros numéricos. En la teoría de la complejidad computacional, la fuerte NP-completitud es una propiedad de los problemas computacionales que es un caso especial de NP-completitud. Un problema computacional general puede tener parámetros numéricos. Por ejemplo, la entrada para el problema de empaquetado binario es una lista de objetos de tamaños específicos y un tamaño para los contenedores de los objetos (estos tamaños son parámetros numéricos). Algunos problemas fuertemente NP-completos pueden ser fáciles de resolver, pero en la práctica es más probable encontrarse con casos difíciles.
dct:subject
dbc:Computational_complexity_theory dbc:Complexity_classes dbc:Strongly_NP-complete_problems
dbo:wikiPageID
6319351
dbo:wikiPageRevisionID
1107142190
dbo:wikiPageWikiLink
dbr:List_of_knapsack_problems dbr:FPTAS dbr:Weakly_NP-complete dbr:Computational_complexity_theory dbr:Bin_packing dbr:Unary_numeral_system dbr:0-1_Knapsack_problem dbc:Computational_complexity_theory dbr:Exponential_function dbr:Fully_polynomial-time_approximation_scheme dbc:Complexity_classes dbr:Positional_notation dbr:Pseudo-polynomial_time dbr:NP-complete dbc:Strongly_NP-complete_problems dbr:NP-hard dbr:Dynamic_programming
owl:sameAs
n9:4vuyc dbpedia-es:Totalmente_NP-completo yago-res:Strong_NP-completeness dbpedia-pl:Problem_silnie_NP-zupełny dbpedia-pt:Fortemente_NP-completo wikidata:Q7624684 dbpedia-fa:ان-پی_کامل_قوی freebase:m.0g0vrx
dbp:wikiPageUsesTemplate
dbt:Strong_and_weak_NP_hardness dbt:Reflist
dbo:abstract
In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing problem is a list of objects of specific sizes and a size for the bins that must contain the objects—these object sizes and bin size are numerical parameters. A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input. A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it; in combinatorial optimization, particularly, the phrase "strongly NP-hard" is reserved for problems that are not known to have a polynomial reduction to another strongly NP-complete problem. Normally numerical parameters to a problem are given in positional notation, so a problem of input size n might contain parameters whose size is exponential in n. If we redefine the problem to have the parameters given in unary notation, then the parameters must be bounded by the input size. Thus strong NP-completeness or NP-hardness may also be defined as the NP-completeness or NP-hardness of this unary version of the problem. For example, bin packing is strongly NP-complete while the 0-1 Knapsack problem is only weakly NP-complete. Thus the version of bin packing where the object and bin sizes are integers bounded by a polynomial remains NP-complete, while the corresponding version of the Knapsack problem can be solved in pseudo-polynomial time by dynamic programming. From a theoretical perspective any strongly NP-hard optimization problem with a polynomially bounded objective function cannot have a fully polynomial-time approximation scheme (or FPTAS) unless P = NP. However, the converse fails: e.g. if P does not equal NP, knapsack with two constraints is not strongly NP-hard, but has no FPTAS even when the optimal objective is polynomially bounded. Some strongly NP-complete problems may still be easy to solve on average, but it's more likely that difficult instances will be encountered in practice. Problem silnie NP-zupełny (ang. Strongly NP-Complete) to taki problem decyzyjny, który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje NP-zupełny. Istnienie algorytmu pseudowielomianowego dla dowolnego problemu silnie NP-zupełnego implikowałoby równość P=NP, a więc jest uważane za wysoce nieprawdopodobne. Natomiast problemy silnie NP-zupełne pozostałyby NP-zupełne nawet przy kodowaniu unarnym, stąd też są również znane jako problemy jedynkowo NP-zupełne. Em Complexidade computacional, NP-completude forte é uma propriedade computacional de problemas que é um caso especial de NP-completude. Um problema computacional geral pode ter parâmetros numéricos. Por exemplo, a entrada para o problema de empacotamento de caixas é uma lista de objetos de tamanhos específicos e um tamanho para a caixa que deve conter os objetos — estes tamanhos de objetos e tamanhos de caixas são parâmetros numéricos. Um problema é dito ser fortemente NP-completo, se ele permanece NP-completo mesmo quando todos os seus parâmetros numéricos são delimitados por um polinômio no comprimento da entrada. Um problema é dito ser fortemente NP-difícil se um problema fortemente NP-completo tem uma redução polinomial para ele; em otimização combinatória, particularmente, a frase “fortemente NP-difícil” é reservada a problemas que não se sabe ter uma redução polinomial a outro problema fortemente NP-difícil.Normalmente parâmetros numéricos para um problema são dados em um Sistema de numeração binário, então um problema de entrada tamanho n pode conter parâmetros cujo tamanho seja exponencial em n. Se nós redefinirmos o problema para ter os parâmetros dados em notação unária, então os parâmetros dever estar delimitados pelo tamanho da entrada. Assim, NP-completude forte ou NP-dificuldade podem também ser definidas como a NP-completude ou NP-dificuldade desta versão unária do problema. Por exemplo, o problema do empacotamento de caixas é fortemente NP-completo enquanto o Problema da mochila é apenas fracamente NP-completo. Assim, a versão do problema de empacotamento de caixas onde o tamanho do objeto e o tamanho da caixa são inteiros delimitados por um polinômio continua NP-completo, enquanto a versão correspondente do problema da mochila pode ser resolvido em tempo pseudo-polinomial por Programação dinâmica. Enquanto problemas fracamente NP-completos possam admitir soluções eficientes na pratica com tanto que suas entradas sejam de magnitude relativamente pequena, problemas fortemente Np-completos não admitem soluções eficientes nestes casos. De uma perspectiva teórica, qualquer problema fortemente NP-dificil com uma função objetiva polinomialmente delimitada não pode ter um esquema de aproximação total em tempo polinomial a menos que P=NP. Entretanto, o inverso não ocorre: e.g se P não for igual a NP, o problema da mochila com duas restrições não é fortemente NP-difícil, mas não tem um esquema de aproximação total em tempo polinomial mesmo quando o objetivo ótimo é polinomialmente delimitado. Alguns problemas fortemente NP-completos podem ser fáceis de resolver na média, mas é mais provável que dificuldades serão encontradas na prática.A menos que P = NP (P versus NP) não existe esquema de aproximação total em tempo polinomial para os problemas fortemente NP-completos. En la teoría de la complejidad computacional, la fuerte NP-completitud es una propiedad de los problemas computacionales que es un caso especial de NP-completitud. Un problema computacional general puede tener parámetros numéricos. Por ejemplo, la entrada para el problema de empaquetado binario es una lista de objetos de tamaños específicos y un tamaño para los contenedores de los objetos (estos tamaños son parámetros numéricos). Un problema se dice que es fuertemente NP-completo si sigue siéndolo incluso cuando todos sus parámetros numéricos están acotados por un polinomio en función de la longitud de la entrada.​ Se dice que un problema es fuertemente NP-difícil si un problema fuertemente NP-completo tiene una reducción polinómica a este; en la optimización combinatoria, en particular, la frase fuertemente NP-difícil se reserva para los problemas que no se sabe si tienen una reducción a otro problema fuertemente NP-completo. Los parámetros numéricos de un problema normalmente se dan en la notación binaria, por lo que un problema de tamaño de entrada n pueden contener parámetros cuyo tamaño es exponencial en n. Si se redefine el problema para tener los parámetros dados en notación unaria, entonces los parámetros deben ser acotados por el tamaño de entrada. Por lo tanto, la fuerte NP-completitud o NP-dureza también se pueden definir como NP-completitud o NP-dureza de la versión unaria del problema. Por ejemplo, el empaquetado binario es fuertemente NP-completo, mientras que el Problema de la Mochila 0-1 es sólo débilmente NP-completo. Así, la versión de empaquetado binario donde los tamaños de objeto y tamaño binario son números enteros asociados a un polinomio es NP-completa, mientras que la versión correspondiente del Problema de la Mochila puede ser resuelto en tiempo polinómico mediante el uso de la programación dinámica. Mientras que los problemas débilmente NP-completos pueden admitir soluciones eficientes en la práctica siempre que sus entradas son de magnitud relativamente pequeña, los problemas fuertemente NP-completos no admiten soluciones eficientes en estos casos. Desde el punto de vista teórico, cualquier problema de optimización fuertemente NP-duro con una función objetivo polinómica asociada, no puede tener un esquema de aproximación de tiempo totalmente polinómico, a menos que P = NP.​ Sin embargo, lo contrario no se cumple: por ejemplo, si P no es igual a NP, el problema de la mochila con dos restricciones no es fuertemente NP-duro, pero no tiene un esquema de aproximación de tiempo totalmente polinómico, incluso cuando el óptimo es acotado polinómicamente.​ Algunos problemas fuertemente NP-completos pueden ser fáciles de resolver, pero en la práctica es más probable encontrarse con casos difíciles. A menos que P = NP, no hay un esquema de aproximación de tiempo totalmente polinómico para los problemas fuertemente NP-completos.​
gold:hypernym
dbr:Property
prov:wasDerivedFrom
wikipedia-en:Strong_NP-completeness?oldid=1107142190&ns=0
dbo:wikiPageLength
4037
foaf:isPrimaryTopicOf
wikipedia-en:Strong_NP-completeness
Subject Item
dbr:Independent_set_(graph_theory)
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Strongly_NP-complete
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
dbo:wikiPageRedirects
dbr:Strong_NP-completeness
Subject Item
dbr:Identical-machines_scheduling
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Partition_problem
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Succinct_game
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:3-partition_problem
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Bin_packing_problem
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Parallel_task_scheduling
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
Subject Item
dbr:Strongly_NP-hard
dbo:wikiPageWikiLink
dbr:Strong_NP-completeness
dbo:wikiPageRedirects
dbr:Strong_NP-completeness
Subject Item
wikipedia-en:Strong_NP-completeness
foaf:primaryTopic
dbr:Strong_NP-completeness