Indicwiki: 1 revision imported from :alpha:Template:Strong_and_weak_NP_hardness

2023-08-10T07:33:44Z

1 revision imported from alpha:Template:Strong_and_weak_NP_hardness

← Older revision	Revision as of 13:03, 10 August 2023
(No difference)

alpha>Indicwiki: Created page with "== Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms == Assuming P ≠ NP, the following are true for computational problems on integers:{{cite w..."

2023-07-25T19:52:21Z

Created page with "== Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms == Assuming P ≠ NP, the following are true for computational problems on integers:<ref>{{cite w..."

New page

== Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms ==
Assuming P ≠ NP, the following are true for computational problems on integers:<ref>{{cite web |last1=Demaine |first1=Erik |title=Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2 |url=http://courses.csail.mit.edu/6.890/fall14/lectures/L02.html}}</ref>

* If a problem is [[weakly NP-hard]], then it does not have a [[weakly polynomial time algorithm]] (polynomial in the number of integers and the ''number of bits'' in the largest integer), but it may have a pseudopolynomial time algorithm (polynomial in the number of integers and the ''magnitude'' of the largest integer). An example is the [[partition problem]]. Both weak NP-hardness and weak polynomial-time correspond to encoding the input agents in [[binary coding]].

* If a problem is [[strongly NP-hard]], then it does not even have a [[pseudo-polynomial time]] algorithm. It also does not have a [[fully-polynomial time approximation scheme]]. An example is the [[3-partition problem]]. Both strong NP-hardness and pseudo-polynomial time correspond to encoding the input agents in [[unary coding]].<noinclude>
{{documentation
|content=
{{no documentation}}
[[Category:Computer science templates]]
[[Category:Mathematics templates]]
}}
</noinclude>

Template:Strong and weak NP hardness - Revision history

Indicwiki: 1 revision imported from :alpha:Template:Strong_and_weak_NP_hardness

alpha>Indicwiki: Created page with "== Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms == Assuming P ≠ NP, the following are true for computational problems on integers:{{cite w..."