The difference between polynomial-time many-one and truth-table reducibilities on distributional problems

DOI10.1007/S00224-002-1025-YzbMATH Open1041.68047OpenAlexW2003644251MaRDI QIDQ1849751FDOQ1849751

Authors: Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 

Publication date: 1 December 2002

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-002-1025-y

Recommendations

• scientific article; zbMATH DE number 1688354
• Relating Equivalence and Reducibility to Sparse Sets
• scientific article; zbMATH DE number 512799
• Comparing Reductions to NP-Complete Sets
• On the theory of average case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: The difference between polynomial-time many-one and truth-table reducibilities on distributional problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849751)