Cont: NP-hard or not: partition with irrational input or parameter

Question

Please take a look at NP-hard or not: partition with irrational input or parameter first.

In Will irrational parameters make a problem not well-defined on complexity, I got an answer of "No". Then I checked that some well-defined problems indeed have irrational paprameters(e.g., In the sum of square root problem, it has square roots).

Now I want to use this "property" (irrational parameters donot make a problem ill-defined on complexity) to modify method 1 such that determining the complexity of original problem is well-defined in some cases and it is NP-complete.

More concretely, suppose that $x_*$ in method 1 is actually $0.52+\sqrt{2}\times 10^{-10}$. Then we ask such a problem:

Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

• ​$a_1,...,a_{n+2}$ are positive and rational,

find a set $S\subseteq N$, such that $f(S)=0.52+\sqrt{2}\times 10^{-10}$, where $f(S)=\sum_{i=1}^n a_i \textbf{I}_{i \in S} + (0.51+\sqrt{a_{n+1}}\times 10^{-10})\textbf{I}_{n+1 \in S}+ (0.47-\sqrt{a_{n+2}}\times 10^{-10})\textbf{I}_{n+2 \in S}$ and $\textbf{I}$ is an indicator function.

Then for such a problem, we can argue that it is NP-complete, since there is one instance with rational inputs satisfying

$\sum_{i=1}^n a_i = 0.02$ and $a_{n+1}=a_{n+2}=2$.

Is this correct?

Answer 1

Without answering your specific question, let me comment on a basic matter that I see appearing in several of your questions. Trying to reason about this as "irrational parameters do or don't make the problem ill-defined" seems likely to be confusing.

Instead, back up and understand the fundamentals. The fundamentals are that we need to specify a problem precisely before we can ask for its running time. How do we specify a problem? The most fundamental way is as a decision problem, and a decision problem is a formal language: a subset of $\{0,1\}^*$. Thus, the problem is: given a string $x \in \{0,1\}^*$, answer whether it is in the language $L$. More generally, if you want to discuss algorithms for problems that produce multiple bits of output, a problem specifies a function $f:\{0,1\}^* \to \{0,1\}^*$. In other words, given any bit-string that is the input, the function $f$ tells us a bit-string that is the desired output.

So, to specify a problem carefully, you specify that mapping $f$. Usually, this is done by specifying the input and how it is represented as a binary string (as a convenience, this latter step is often omitted if it is obvious how to do it, but it's exactly this step that is tripping you up, so for you, do not omit it), and by specifying the correct output (as a function of the input) and how it is represented as a binary string (again, you better not omit this).

When you start talking about irrational numbers, you are going to run into the problem that irrational numbers cannot be represented as a binary string. There is no encoding of numbers that enables you to encode all possible irrational numbers and that ensures that all encodings are finite. Thus, if your problem statement says "the input is an irrational number...", you are going to have a problem.

Then, to prove that a question is NP-complete, you construct a reduction. So, go do that. Don't try to prove it with one line ("there is one instance with rational inputs satisfying..") constructed in an ad-hoc way -- instead, explicitly construct the reduction. If you understand the concepts, you should be able to tell whether your reduction is correct or not, without needing to ask us.

Before asking another in this line of questions, I suggest that you study basic material on P, NP, reductions, and complexity classes. Make sure you understand it at the basic level, before trying to apply it to your specific problem. Textbooks are written to make it easier to understand these concepts in the context of some simpler problems, and that will make it easier to pick up than to try to both learn the concepts and apply it to your harder problem at the same time.