polynomial-time many-one reduction
C44231
concept
A polynomial-time many-one reduction is a function computable in polynomial time that transforms instances of one decision problem into instances of another such that the original instance is a "yes" instance if and only if the transformed instance is a "yes" instance.
All labels observed (1)
| Label | Occurrences |
|---|---|
| polynomial-time many-one reduction canonical | 1 |
Description generation (CDg)
The one-sentence description above was generated by prompting gpt-5.1 with the class name and this instruction.
Instruction
generate a one-sentence description for a given conceptual class. # Response Format Return only the sentence: "Description: [one-sentence description of the conceptional class]"
Input
Class: polynomial-time many-one reduction
Generated description
A polynomial-time many-one reduction is a function computable in polynomial time that transforms instances of one decision problem into instances of another such that the original instance is a "yes" instance if and only if the transformed instance is a "yes" instance.
Instances (1)
| Instance | Via concept surface |
|---|---|
|
Karp reductions
surface form:
Karp reduction
|
— |