0
$\begingroup$

Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP?

That is, an algorithm that doesn't rely on patterns/redundancy occurrence in data to work, but instead on some clever mathematical operations.

Such algorithm will be able to compress random data, but of course, not every data, since it will need to output the variables that the decompression part of it will run mathematical operations on to rebuild the original data.

Please try not be condescending in your answer. I'm a programmer too, but I'm aware I know little compared to most of you here.

I just want to know if such algorithm proves P=NP.

I'm not asking about the possibility of the algorithm, so try not to tell me especially in a condescending way it is impossible.

I'm very aware of the impossibility based on patterns/redundancy reliance for the current algorithms to work on.

I'm working on an alternative method that uses pure mathematics right now. No reliance on data redundancy. But I won't say I have the algorithm. Sometimes you thought you've had something but turns out it's just another mirage.

If it's really a practical and better alternative to the current ones, I will edit this post and post a link to it for you to review before I file a patent (1 year grace in the US after disclosure)

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Just to be clear question at hand is the following:

Let $c$ be a constant. Does the existence of an algorithm that takes a string $x \in \{0,1\}^*$ as input and outputs a string $f(x) \in \cup_{i=0}^c \{0,1\}^c$ such that $f$ is invertible (i.e., there exists some function $f^{-1}$ such that $f^{-1}(f(x)) = x$ for every $x$) imply that $\mathsf{P}=\mathsf{NP}$?

Formally, the answer to your question is "yes" but you might find the argument unsatisfactory: since there can be no algorithm with the properties above, the question is equivalent to "is it true that $\mathsf{false}$ implies $\mathsf{P}=\mathsf{NP}$?", which is clearly true (see principle of explosion).

If you want a more direct proof you can reason as follows. Take any $\mathsf{NP}$-complete language $L$ and consider the language $L' \in \{f(x) \mid x \in L\}$. Since $f$ is injective, $|L| \le |L'| < 2^{c+1}$ implying that $L$ is a finite language and hence it belongs to $\mathsf{P}$.

$\endgroup$
3
  • $\begingroup$ "Is it true that false implies P = NP?". If I understand you clearly, the argument is if this impossibility somehow becomes a possibility, then P = NP is true. The impossibility which can never become a possibility right? Please permit my naive questions. $\endgroup$ May 20 at 15:37
  • $\begingroup$ And note please, I have some stupid questions. I'm just going into the theoretical part of CS. I'm an amateur programmer who learned by reading through programming articles online. Hence my naive questions. $\endgroup$ May 20 at 15:43
  • $\begingroup$ "is if this impossibility somehow becomes a possibility, then P = NP is true". I'm not sure if I'd phrase it as "an impossibility becomes a possibility" since this is absurd. The point is that once you assume a contradictionthen everything can be proven true (and also false). $\endgroup$
    – Steven
    May 21 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.