0
$\begingroup$

I am trying to reason about weak NP-hardness using pseudopolynomial reductions.

Suppose:

  • Problem A is weakly NP-hard.
  • There exists a pseudopolynomial-time reduction from A to another
    problem B.
  • Problem B admits a pseudopolynomial-time algorithm.

Under these assumptions:

Can we conclude that problem B is weakly NP-hard?

More generally, how do pseudopolynomial reductions interact with the notion of weak NP-hardness? Are there standard results or references clarifying what can (or cannot) be inferred in this setting?

Improve this question
$\endgroup$
1
  • $\begingroup$ So, how exactly do you define a pseudopolynomial-time reduction? $\endgroup$ Commented Feb 12 at 12:48

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.