This weeks biggest news.
The ETH is False — OpenAI says. OpenAI has come up with a proof now in consideration.
Here are my views on P=NP question in today’s world, world in 2026 where we have sophisticated machines not limited as in 2000s or before.
So, what is the P=NP question now? Given that we are living in a world where rapid computation is available to us. We have huge cloud computing; we are in a totally different era, when we can see the below-mentioned complexity of the satisfiability problem (the number of subsets of a set n or the number of varieties of inputs for the CNF problem):
Give one of these following n terms to one thread each solved in polynomial time which can be deterministic if ordered.
If we have n machines, or n threads, then each thread can be given a polynomial-time problem. Each of the following can be deterministic polynomial series,
This can prove satisfiability in today’s near infinite-machine concept: polynomial time with complexity n/2 if n is decent; otherwise, assign the polynomials to each server until n is decent, each being a 2^n problem then. When n is really huge, each can be a 2^n problem on a limited number of say m machines. Hence each with a NP Complete solution!
However, in the case when ETH was made, we had limited memory and computing capabilities. The proofs can run with constraints that memory and hardware are limited! So we can still hold the theorems and results with limited hardware as true but on limited machines. In today’s modern times, when we have Quantum computing and huge data centers, we can’t think for n as limit of one million? Should we? Time to rethink! Time to design these computations on new machines, new servers, new hardware? Why not think in this direction?
In today’s world, P=NP does not need an oracle.
Indeed, we can use Cook’s Theorem or prove it as an ordered assignment to the Kth Server, the thread order, to get a unique assigned combination. Means P=NP.
Details:
If T(n) is the time for solving a problem with n inputs, and if this time is bounded above by a function f with input n, then we say T(n)= O(f(n)).
When an algorithm’s result is uniquely defined, it is called deterministic; otherwise, it is called non-deterministic.
These can be divided into two groups:
I. Polynomial time algorithms. Problems whose algorithms are bounded by low-degree polynomials and solved deterministically. (P (Polynomial) problems)
Examples are: Searching on an array of size n is O(log n), sorting is O(n log n), and matrix multiplication is O(n^ 2.81)
II. Non-Polynomial time algorithm: No polynomial-time algorithm exists for this group of problems. The best-known algorithms are non-polynomial and can’t be solved deterministically. (NP problems)
Examples include the Traveling Salesperson Problem and the Knapsack problem, whose best algorithms are non-polynomial: O(n² 2^n) and O(2^n/2), respectively.
Even polynomial algorithms can be non-deterministic, while non-polynomial algorithms can be solved by polynomial-time non-deterministic algorithms. P is contained in NP because, by definition, it is a special case of NP.
Question:
Is P = NP, or is P not equal to NP? For each problem in NP, does there exist a P algorithm that is yet to be discovered?
Many problems that are in NP are computationally related to each other.
CNF Satisfiability Problem: A formula in CNF (Conjunctive Normal Form) is satisfiable if it is true for some assignment of boolean variables. Complexity: O(2^n)
3-SAT problem: A formula is expressed in Conjunctive Normal Form (CNF) where each clause contains exactly three literals.
Cook’s Theorem: CNF Satisfiability is in P iff P = NP.
ETH is proved false by OpenAI this week.
NP-Hard problems: A problem is NP Hard if and only if the CNF satisfiability problem reduces in polynomial time to L.
NP-Complete: A problem is NP complete if and only if L is NP Hard and L is NP.
NP-complete problems are NP-hard, but vice versa is not true.
NP-Complete problems: A problem is NP-complete if and only if it is NP-hard and it is in NP.
Some problems are NP-hard but not NP-complete. Example: the Halting problem (there exists no algorithm in P to solve it, even in a non-deterministic way).
Thank you for reading.
Subscribe for updates.
