Basically, there are 3 main barriers to proving P not equaling NP.
One, you have to actually show that there exists a hard function that isn’t in P, and it’s not enough to prove that there are exponentially many hard functions, because it might be that a circuit computing an NP-complete problem has a linear time bound.
And natural proofs argue that unless cryptographically hard functions don’t exist, the common way to prove circuit lower bounds also can’t prove P vs NP (Technical details are below:)
Also, both of the strategies cannot relativize or algebrize, where relativization means that if we give a fixed oracle tape O consisting of a single problem you can solve instantly to all parties doesn’t change the conclusion for all oracle tapes O.
Many results like this, including possibly your attempts to prove via counting arguments almost certainly relativize, and even if they don’t, they algebrize, and the technical details are below for algebrization are here, since I already explained relativization above.
Basically, there are 3 main barriers to proving P not equaling NP.
One, you have to actually show that there exists a hard function that isn’t in P, and it’s not enough to prove that there are exponentially many hard functions, because it might be that a circuit computing an NP-complete problem has a linear time bound.
And natural proofs argue that unless cryptographically hard functions don’t exist, the common way to prove circuit lower bounds also can’t prove P vs NP (Technical details are below:)
https://en.wikipedia.org/wiki/Natural_proof
Also, both of the strategies cannot relativize or algebrize, where relativization means that if we give a fixed oracle tape O consisting of a single problem you can solve instantly to all parties doesn’t change the conclusion for all oracle tapes O.
Many results like this, including possibly your attempts to prove via counting arguments almost certainly relativize, and even if they don’t, they algebrize, and the technical details are below for algebrization are here, since I already explained relativization above.
https://www.scottaaronson.com/papers/alg.pdf
But that’s why proving P vs NP is so hard technically.