“P and NP are two prominent complexity classes, and the question
whether or not they are equal is one of the most important ones in
computer science. This paper, by its title and beginning of abstract,
gives the (false) impression that it solves this important open
problem. Instead, it defines two different classes of problems (that
in this report I’d call “relativised P” and “relativised NP”),
and argues that those classes are more deserving of the names “P” and “NP”.
It then argues that those two classes are different.

Even when the author would be right that the new classes are more
interesting then the old ones, and even when from first principles
“P” and “NP” would be the best names for these classes, i.m.o. it is
not acceptable to conduct such a renaming of concepts. The old names
“P” and “NP” are widely used and understood, and redefining everything
now would be a bad source of confusion. In particular, the author does
not claim to have solved the old-terminology “P=NP?”-problem, and for
this reason no paper can be accepted whose title suggest otherwise.

Above Prop. 1 the author argues against giving his new complexity
class (relativised NP) any other name than “NP”. He says it is would
confuse and damage the clearness of notation. My position is that the
original name of the old class NP should stay, simply because it was
first. This follows tradition in all scientific fields. The confusion
and damage to the clearness of notation proposed by the author is much
greater.

Since the author appears unwilling to compromise regarding the names
of the complexity classes he tries to separate in this paper, his work
cannot possibly be accepted at CATS or any other respectable
scientific forum. This is a pity, because good ideas may be part of
the author’s work, and these ideas will have a hard time of being
evaluated in their own right when they stand in the shadow of a bogus
suggestion that the P vs. NP problem is being solved.
I therefore urge the author to rename his complexity classes and
discuss his findings in a (thereby) less controversial way.

—

As for the new ideas themselves, in Barbosa’s framework a problem is
given by a pair of languages (L, L_z), the first included in the second.
A decision algorithm for such a problem, when fed as input a word in L_z,
outputs 1 if the word is in L, and 0 otherwise.

For instance, the emptiness problem of context-free languages can be
represented in this way: L_z is the set of all string-representations
of context-free languages, and L is the subset of those strings in L_z
with the property that the CFL they represent is empty.

The difference between Barbosa’s approach and that of classical
complexity theory is in answer to the question: “But what should the
algorithm do if it is fed a string that doesn’t even represents a
context-free language?”. Barbosa’s answer, essentially, is
“This will not come up; we only are going to feed it strings, known to
by in L_z (i.e. know to represent context-free languages)”.
A different answer, that’s just as powerful as Barbosa’s, is:
“We couldn’t care less”. That is, if the algorithm is fed a string
that does represent a CFL, then the algorithm should return 1 iff that
CFL is empty; but it it is fed a string that doesn’t represent a CFL,
it may do whatever.
This contrasts with the classical approach, in which some arbitrary
decision about these non-representing strings need to be made.
For in old-fashioned complexity theory, a problem is given by just the
set L, thereby disregarding the contextual information provided by L_z.
Normally, the algorithm is required to return 0 for all strings that
do not represent context-free languages. Thus, the problem that is
actually solved is not “Given a CFL, is it empty?”
but “Given a string, is it the representation of a empty CFL?”
The answer, then, can be negative for two entirely different reasons:
- either the string fails to represent a CFL,
- or the represented CFL fails to be empty.

Seen in this way, I find Barbosa’s approach quite natural compared to
the classical one, and I think we should be open for new insights that
it would bring. However, I do not want to be so ‘open’ as to completely
discard the old complexity theory, and redefine its named concepts to
apply to the new one.

Even disregarding naming issues, I do not buy the author’s proof that
XG_SAT is in relativised NP. For L_r to be decidable in polynomial
time, there needs to be a single (fixed) polynomial, such that for any
input (composed of y *and* x) the TM is going to halt within the
bounds specified by that polynomial. Making the polynomial dependant
on the x-component of the input is not acceptable.

—

Question to the author:
Given L and L_z, is it the case that “the L_z-language L is in NP”
(your terminology) iff there exists a language L’ that is in NP (in
the standard terminology) such that L is the intersection of L’ and L_z?
If this is true, it would be good to prove it, as such a connection
would connect your complexity theory with the standard one, and
thereby (possible) increase its understanding by people that are
predisposed towards classical complexity theory.”

None…