Timeline for how can i say a given problem is in co-NP using it's definition?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 24, 2019 at 12:49 | comment | added | dkaeae | @Euclid Problems do not have "corresponding languages". A decision problem is a language. Under the assumption mentioned in the answer, what you are saying is true: both a problem and its complement are valid problems (simply because they are both subsets of $\{0,1\}^\ast$). If they are promise problems, however, things are a bit different (but may be defined in equivalent fashion). | |
| Jan 24, 2019 at 12:06 | comment | added | user92484 | I'm still scratching my head a bit. Can't we then say that every problems corresponding language is the complement of any other problems corresponding language (since were excluding the not valid instances)? | |
| Jan 24, 2019 at 8:31 | history | answered | dkaeae | CC BY-SA 4.0 |