NP-equivalent
id:
np-equivalent-288-5060888
title:
NP-equivalent
text:
In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems. For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integers, FIND-SUBSET-SUM is the problem of finding some nonempty subset of the integers that adds up to zero. This optimization problem is similar to the decision problem SUBSET-SUM. Given a set of integers, SUBSET-S
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/NP-equivalent
date created:
date modified:
2023-01-11T11:55:39Z
main entity:
{"identifier":"Q1961336","url":"https://www.wikidata.org/entity/Q1961336"}
image:
fields total:
13
integrity:
13