Gap reduction
id:
gap-reduction-198-4749787
title:
Gap reduction
text:
In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Gap_reduction
date created:
date modified:
2022-04-12T07:35:01Z
main entity:
{"identifier":"Q25303752","url":"https://www.wikidata.org/entity/Q25303752"}
image:
fields total:
13
integrity:
13