Re: Is there an EXPSPACE complete language?

>>But if such class C has complete language L then:
>>EXPTIME^L <= EXPSPACE^L <= C <= P^L
>>EXPSPACE^L <= C: since C is closed under composition with exponential
>>functions
>>C <= P^L: by definition

>You're right, I didn't think this through. The "standard complete language"
>as I stated it is incorrect. For NP, for example, the standard complete
>language is really

Here is a quite presume thought.
It's proven that if PH (polynomial hierarchy) does NOT have a complete
language then P != NP.
Otherwise PH will collapse to P which makes SAT PH complete.

I (boldly) thought that it might be possible to show that PH doesn't
have complete language using "similar" considerations.

Is it considered to be "harder" problem than P != NP?

Thanks,
Rani

.

Relevant Pages

  • Re: Is C99 the final C? (some suggestions)
    ... > that someone will try compile their stuff on an old compiler. ... > because the ANSI standard obsoleted them, and everyone picked up the ANSI ... fixed by using another language. ... >>are multiplying two expressions of the widest type supported by your ...
    (comp.lang.c)
  • Re: subroutine stack and C machine model
    ... They could have standardized that the language would be ... getting the facts wrong anyway. ... And the answer, for the Schildt books, is that they consistently produced ... to C start with the standard. ...
    (comp.lang.c)
  • Re: Two Questions about "strlen", "strcat" and "strcpy"
    ... >> No. zero terminated strings is the whole problem in the first place. ... > OR length prefixed strings the language would retain compatibility ... is not easily duplicated with the old standard then it will foster interest. ... The C standards committee is dead. ...
    (comp.lang.c)
  • Re: Forth Frustrations
    ... How would they even know what they are without being language lawyers? ... standard systems and a large number of nonstandard ones. ... interpreter, ... They set up four states -- HOST INTERPRETER COMPILER ...
    (comp.lang.forth)
  • Re: Is C99 the final C? (some suggestions)
    ... >> because the ANSI standard obsoleted them, and everyone picked up the ANSI ... > fixed by using another language. ... programmers managing the meaning of the symbols for more generic operators. ... According to a paper by Intel, widening multiply accounts for something like ...
    (comp.lang.c)