b'\n_START_ARTICLE_\nProblem silnie NP-zupe\xc5\x82ny\n_START_PARAGRAPH_\nProblem silnie NP-zupe\xc5\x82ny (ang.\xc2\xa0Strongly NP-Complete) to taki problem decyzyjny, kt\xc3\xb3ry nawet przy ograniczeniu maksymalnej warto\xc5\x9bci wyst\xc4\x99puj\xc4\x85cych w jego opisie liczb pozostaje NP-zupe\xc5\x82ny._NEWLINE_Istnienie algorytmu pseudowielomianowego dla dowolnego problemu silnie NP-zupe\xc5\x82nego implikowa\xc5\x82oby r\xc3\xb3wno\xc5\x9b\xc4\x87 P=NP, a wi\xc4\x99c jest uwa\xc5\xbcane za wysoce nieprawdopodobne. Natomiast problemy silnie NP-zupe\xc5\x82ne pozosta\xc5\x82yby NP-zupe\xc5\x82ne nawet przy kodowaniu unarnym, st\xc4\x85d te\xc5\xbc s\xc4\x85 r\xc3\xb3wnie\xc5\xbc znane jako problemy jedynkowo NP-zupe\xc5\x82ne.\n_START_SECTION_\nDowodzenie silnej NP-zupe\xc5\x82no\xc5\x9bci\n_START_PARAGRAPH_\nDowodzenie silnej NP-zupe\xc5\x82no\xc5\x9bci bezpo\xc5\x9brednio z definicji wymaga\xc5\x82oby znalezienia wielomianu spe\xc5\x82niaj\xc4\x85cego warunki okre\xc5\x9blone w definicji. Niejednokrotnie okazuje si\xc4\x99 to jednak nie\xc5\x82atwe._NEWLINE_W przypadku problem\xc3\xb3w, kt\xc3\xb3re nie s\xc4\x85 problemami liczbowymi wystarczy jednak dowie\xc5\x9b\xc4\x87 tylko ich NP-zupe\xc5\x82no\xc5\x9bci. Za\xc5\x9b w przypadku problem\xc3\xb3w liczbowych wykorzystuje si\xc4\x99 transformacje pseudowielomianowe do sprowadzenia pewnego znanego problemu silnie NP-zupe\xc5\x82nego do danego problemu, kt\xc3\xb3rego siln\xc4\x85 NP-zupe\xc5\x82no\xc5\x9b\xc4\x87 si\xc4\x99 dowodzi, podobnie jak wykorzystuje si\xc4\x99 transformacje wielomianowe przy dowodzeniu NP-zupe\xc5\x82no\xc5\x9bci.'