On symmetric differences of NP-hard sets with weakly P-selective sets
type: Item
instance of: scholarly article
title: On symmetric differences of NP-hard sets with weakly P-selective sets
zbMATH Open document ID: 0805.68042
DOI: 10.1016/0304-3975(93)90292-2
author: Bin Fu
author: Hong-zhou Li
published in: Theoretical Computer Science
publication date: 1995-01-26T00:00:00Z
review text: The possibility and consequences are studied of having an NP-hard set that forms a symmetric difference with an ``easy'' set (like a weakly \(p\)-selective set) that is of ``low information content''. Especially, it is shown that the existence of an NP-hard set \(A\) (with respect to many- one reducibility) that forms a symmetric difference to a weakly \(p\)- selective set \(B\), such that both \(A-B\) and \(B-A\) are bounded-truth-table reducible to a sparse set implies \(\text{P}=\text{NP}\). The proof is based on the tree pruning techniques by Mahaney and Fortune.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 501183
zbMATH Keywords: sparse sets
zbMATH Keywords: NP-hard sets
zbMATH Keywords: weakly \(p\)-selective
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90292-2
OpenAlex ID: W2093889711
cites work: Q3996675
cites work: On Sets Truth-Table Reducible to Sparse Sets
cites work: A Note on Sparse Complete Sets
cites work: On lower bounds of the closeness between complexity classes
cites work: Semirecursive Sets and Positive Reducibility
cites work: On self-reducibility and weak P-selectivity
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Some observations on NP real numbers and P-selective sets
cites work: Reductions on NP and p-selective sets
cites work: On polynomial-time truth-table reducibility of intractable sets to P-selective sets
cites work: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
Recommended article: Q4779177
Recommended article: On reducibility and symmetry of disjoint NP pairs.
Recommended article: On Hadamard difference sets with weak multiplier minus one
Recommended article: On non-symmetric relative difference sets
Recommended article: A note on closeness between \(NP\)-hard sets and \(C_= P\)
Recommended article: Q5315868
Recommended article: On the existence of hard sparse sets under weak reductions
Recommended article: Partial difference sets from quadratic forms and $p$-ary weakly regular bent functions
Recommended article: An extremal problern for set families generated with the union and symmetric difference operations
Recommended article: A survey of partial difference sets
description: scientific article; zbMATH DE number 501183