On limitations of transformations between combinatorial problems

William Slough; Karl Winklmann

doi:10.1007/BF02090395

On limitations of transformations between combinatorial problems

William Slough, Karl Winklmann

Research output: Contribution to journal › Article › peer-review

Original language	American English
Journal	Theory of Computing Systems \/ Mathematical Systems Theory
Volume	24
DOIs	https://doi.org/10.1007/BF02090395
State	Published - Dec 1 1991
Externally published	Yes

Disciplines

Mathematics
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF02090395License: Unspecified

Cite this

@article{181980423f7249bb9b4b7be1ad1c356b,

title = "On limitations of transformations between combinatorial problems",

author = "William Slough and Karl Winklmann",

note = "We define a class of {"}local transformations{"} that includes many transformations from the NP-completeness literature. We then prove (without assuming P≠NP) that this type of transformation is too weak to transform 3SAT or a number of other NP-complete problems into 2SAT or a number of other problems in P.",

year = "1991",

month = dec,

day = "1",

doi = "10.1007/BF02090395",

language = "American English",

volume = "24",

journal = "Theory of Computing Systems \/ Mathematical Systems Theory",

}

TY - JOUR

T1 - On limitations of transformations between combinatorial problems

AU - Slough, William

AU - Winklmann, Karl

N1 - We define a class of "local transformations" that includes many transformations from the NP-completeness literature. We then prove (without assuming P≠NP) that this type of transformation is too weak to transform 3SAT or a number of other NP-complete problems into 2SAT or a number of other problems in P.

PY - 1991/12/1

Y1 - 1991/12/1

UR - https://link.springer.com/article/10.1007%2FBF02090395

U2 - 10.1007/BF02090395

DO - 10.1007/BF02090395

M3 - Article

VL - 24

JO - Theory of Computing Systems \/ Mathematical Systems Theory

JF - Theory of Computing Systems \/ Mathematical Systems Theory

ER -

On limitations of transformations between combinatorial problems

Disciplines

Access to Document

Other files and links

Cite this