3 citations · 3 across the 8 of their papers we have counts for
4 papers · 1 filter
Expressibility at the machine level versus structure level: ESO universal Horn Logic and the class P
Prabhu Manyem
We show that ESO universal Horn logic (existential second logic where the first order part is a universal Horn formula) is insufficient to capture P, the class of problems decidabl…
Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version)
Prabhu Manyem
We show that the maximum clique problem (decision version) can be expressed in existential second order (ESO) logic, where the first order part is a Horn formula in second-order qu…
Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate
Prabhu Manyem
In this manuscript, assuming that Graedel's 1991 results are correct (which implies that bounds on the solution values for optimization problems can be expressed in existential sec…
Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes)
Prabhu Manyem
In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as \textbf{P, NP, L and NL}. ~ However, research on the descriptive com…