Skip to main content
Computer Science

Return to Question

edited tags
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Are any languages closed under it's complete complexity classes If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then it'sits complement is X-complete? Why?

I was thinking that it has to do with accepting states in TouringTuring Machine. You should just switch them so the complexity should be the same but I'm not sure.

Are any languages closed under it's complete complexity classes?

I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then it's complement is X-complete? Why?

I was thinking that it has to do with accepting states in Touring Machine. You should just switch them so the complexity should be the same but I'm not sure.

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then its complement is X-complete? Why?

I was thinking that it has to do with accepting states in Turing Machine. You should just switch them so the complexity should be the same but I'm not sure.

Source Link
Milano
Milano
  • 359
  • 1
  • 5
  • 10

Are any languages closed under it's complete complexity classes?

I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then it's complement is X-complete? Why?

I was thinking that it has to do with accepting states in Touring Machine. You should just switch them so the complexity should be the same but I'm not sure.