Hartmanis and Hopcroft's framework for structural complexity treats class membership as a property of formal languages, not of mathematical problems per se, so asserting FACTORIZATION 'is in' NP ∩ coNP without specifying the encoding and decision variant commits a use-mention conflation.
?Rate how convincing each reason is below to see the overall strength.
No one has weighed in yet. Be the first to share reasons for or against this statement.
Sign in or register to share your perspective on this statement.
A problem X is in coNP just in case there exists a polynomial-decidable relation R(x,y) and a polynomial p(x) such that x ∈ X if and only if ∀y ≤ p(|x|) R(x,y).
decision variant(as a choice in how to frame a problem)
A version of a problem phrased as a yes-or-no question, rather than asking you to find a full solution.
encoding(Contrasted with exemplification; characterized as 'internal' predication. E.g., the winged horse encodes the property winged without exemplifying it.)
The mode of predication attributed to non-existent objects, by which such objects bear a property without instantiating it in the ordinary sense.
formal languages(as the objects that complexity theory studies)
Systems of symbols and rules (like programming languages or mathematical notation) where meaning is precise and unambiguous.
structural complexity(as a field of computer science)
The study of how hard different computational problems are and how they relate to each other based on their internal structure.
use-mention conflation(as a logical error being pointed out)
Confusing the difference between *talking about* a word or concept versus *using* the word or concept itself—like saying 'dog' is an animal versus saying the word 'dog' has three letters.