Skip to main content
deleted 78 characters in body; edited title; deleted 12 characters in body
Source Link
Serge Gaspers
  • 5.2k
  • 30
  • 42

What evidence is there that $coR$coRP \neq NP$?

What evidence is there that $coR \neq NP$$coRP \neq NP$?

Update: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

What evidence is there that $coR \neq NP$?

What evidence is there that $coR \neq NP$?

Update: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

What evidence is there that $coRP \neq NP$?

What evidence is there that $coRP \neq NP$?

$coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

deleted 30 characters in body
Source Link
Serge Gaspers
  • 5.2k
  • 30
  • 42

What evidence is there that $coR \neq NP$?

UpdateUpdate: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, the class of languages negative one-sided error machines for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

What evidence is there that $coR \neq NP$?

Update: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, the class of languages negative one-sided error machines for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

What evidence is there that $coR \neq NP$?

Update: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

added 395 characters in body
Source Link
Serge Gaspers
  • 5.2k
  • 30
  • 42

What evidence is there that $coR \neq NP$?

Update: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, the class of languages negative one-sided error machines for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

What evidence is there that $coR \neq NP$?

What evidence is there that $coR \neq NP$?

Update: Sorry for the confusion and thanks Robin. Indeed, I mean by $coR$, also known as $coRP$, the class of languages negative one-sided error machines for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

Source Link
Serge Gaspers
  • 5.2k
  • 30
  • 42
Loading