This is hobby level work, not my job. I wrote this excerpt to share some ideas about Co-NP.
The idea is to pick a problem category in Co-NP, where the correct answer is hard to verify because of circuit complexity, express it as 1-in-k SAT formula, and show there also exists a short certificate, whose length in bits is exactly twice the number of clauses. It might be true or false that all of Co-NP problems have such a short certificate in this form (Co-NP ?= NP), but I show that regardless of that, the short certificate for this problem can be made arbitrarily hard to find, because of the interleaved relationship with NP. Basically, I want to highlight a particular circular dependency between the oracles of NP and Co-NP. The argument to stomp against Co-NP = P is that no TM can hope to attack the problem of searching for the short certificate in subexponential time, because the way I define the problem makes it contain an arbitrary amount of "actual random". Basically, it is one specific recipe to build a "monster" Co-NP problem from a simple certificate.
Now I have many questions for anyone with more formal training than me:
- Has this category of problem been expressed with a different name?
- Is this an obvious dead end or unexplored?
- How can I express the same ideas but more formally against TM capabilities?