Timeline for Examples of bad notation and its consequences
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2023 at 4:30 | comment | added | user21820 | @TimothyChow: That's right; my P^0 was exactly your P[T^∅]. And yes you could solve the issue by making very clear (to students) that P is merely abbreviation for "P^0". The more radical alternative I suggested was just a fun way that allows us to actually retain the usual appearance of these notations except for changing "=" to "≡". XD | |
| Apr 22, 2023 at 1:56 | comment | added | Timothy Chow | @LSpice The trouble with that suggestion is that the sets of languages $\mathsf{P}$ and $\mathsf{NP}$ really are the primary objects of interest. They are extremely robust and "machine-independent." Oracles, at least IMO, are not so interesting in their own right; they're tools for helping us figure out what sorts of things are going to be hard to prove and what sorts of things might be more tractable. | |
| Apr 22, 2023 at 1:43 | comment | added | LSpice | Re, in the spirit of @user21820's suggestion, mightn't a remedy be to regard a complexity class $\mathsf C$ not as a set of languages, but rather as "the machine" in whatever sense; then to denote the corresponding set of languages by, say, $\DeclareMathOperator\Lang{Lang}\Lang(\mathsf C)$, so that $\Lang(\mathsf P) = \Lang(\mathsf{NP})$ obviously need not imply $\Lang(\mathsf P^A) = \Lang(\mathsf{NP}^A)$? | |
| Apr 21, 2023 at 17:29 | comment | added | Esa Pulkkinen | Adding any oracle can change complexity of the classes involved since some problems that are solved with oracle using "magic" oracle operation cannot be simulated with same amount of resources. It's then matter of finding sufficient resources elsewhere to determine if the oracle machines can be simulated without oracle and checking that those simulations do not use too many resources. But adding oracle operation can also complicate matters, since enumerating all possible outputs of the oracle machine is not as simple. For example having oracle produce random bits to produce thread ids => races | |
| Apr 21, 2023 at 11:55 | comment | added | Timothy Chow | @user21820 Rereading more carefully what you wrote, I believe that what I'm suggesting is not so different from your suggestion. Part of what I'm saying is that the "full notation" for $\mathsf{P}$ would be $\mathsf{P}_{T^\varnothing}$. One would use the abbreviation $\mathsf{P}$ only when there is no danger of confusion. | |
| Apr 21, 2023 at 11:51 | comment | added | Timothy Chow | @user21820 Redefining $\mathsf{P}$ and $\mathsf{NP}$ to be something other than complexity classes strikes me as too extreme. But whatever the limitations of my suggestion $\mathsf{P}_{T^A}$, I think it does address the issue I raised. One is not tempted to infer from $\mathsf{P}_{T^\varnothing} = \mathsf{NP}_{T^\varnothing}$ that $\mathsf{P}_{T^A} = \mathsf{NP}_{T^A}$ for all $A$. Or at the very least, the notation alerts you to the fact that $A$ is not being applied to $\mathsf{P}$ or to $\mathsf{NP}$ directly. | |
| Apr 21, 2023 at 7:12 | comment | added | user21820 | Another possible solution is that P and NP and other such terms should be defined as models(!) rather than complexity classes, and then the question of equal classes must be expressed differently, say via "P ≡ NP". It is then clear that it may be that P ≡ NP but P^A ≢ NP^A for some A, just like 6 ≡ 10 (mod 4) but 6/2 ≢ 10/2 (mod 4). | |
| Apr 21, 2023 at 7:08 | comment | added | user21820 | Hmm, I don't like $P_{T^A}$ even more. It doesn't solve the issue you raised... The reason I suggested "P^0" is that as long as you think of "P" as the base model and "P^A" as the result of adding "A" to the base model "P" to get a complexity class, then everything is fine, since "^0" is equivalent to no oracle. Unfortunately, "^0" is really cumbersome. | |
| Apr 21, 2023 at 4:35 | comment | added | Timothy Chow | Minor correction: A complexity class is a set of languages, and a language is a set of strings. | |
| Apr 21, 2023 at 0:49 | comment | added | Timothy Chow | @LSpice Yes. A complexity class is a set of strings. Contrary to what the notation seems to suggest, relativizing to an oracle is not an operation that applies directly to the set of strings; it's a modification of the machine. There may be two different "conditions" which cause the machine to accept equivalent sets of strings, but that doesn't imply that imposing the corresponding conditions on the modified machine will still cause it to accept equivalent sets of strings. | |
| Apr 20, 2023 at 23:39 | comment | added | LSpice | For the benefit of someone whose last computability theory was back in their undergraduate days, what is the wrong step here? Is it that equal complexity classes need not have equal relativisations? | |
| Apr 20, 2023 at 14:28 | comment | added | Timothy Chow | @user21820 I admit I don't have a perfect solution, but I think there ought to be some way to indicate that the oracle is being applied to the machine model and not the language. Maybe something like $\mathsf{P}_{T^A}$ instead of $\mathsf{P}^A$ where $T$ symbolizes the Turing machine model. One might still use $\mathsf{P}^A$ (or maybe $\mathsf{P}_A$) for brevity when there is no danger of confusion, but there should be a way to revert to a more precise notation when necessary to avoid confusion. | |
| Apr 20, 2023 at 13:36 | comment | added | user21820 | Do you have a preferred solution to this? What about P^0 and NP^0? | |
| S Apr 20, 2023 at 4:22 | history | answered | Timothy Chow | CC BY-SA 4.0 | |
| S Apr 20, 2023 at 4:22 | history | made wiki | Post Made Community Wiki by Timothy Chow |