 | Draft article not currently submitted for review.
This is a draft Articles for creation (AfC) submission. It is not currently pending review. While there are no deadlines, abandoned drafts may be deleted after six months. To edit the draft click on the "Edit" tab at the top of the window. To be accepted, a draft should:
It is strongly discouraged to write about yourself, your business or employer. If you do so, you must declare it. Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Last edited by Changruii Mu (talk | contribs) 5 months ago. (Update) |
Introduction edit
Relativization is a fundamental technique in the study of complexity theory and cryptography. It refers to the process of modifying complexity classes by incorporating an "oracle", either as the input or part of the definition of language. We call a result about complexity classes "relativize" if the result mains true even if the complexity class involved in the result is replaced with the respective classes relative to any oracle. All known complexity results made by standard "black box" reduction relativize. On the contrary, there is a few complexity theoretic statements cannot relativize, which means they are true relative to certain oracles and false relative to certain others. The proof on the non-relativization of a statement can be used as an evidence for the difficulty of redolving questions in complexity theory [BGS75][BG81], because it indicates that no techniques which relativizes can prove the statement.