<p>Researchers work under the assumptions they think are more plausible. In the case of complexity theory almost every experts thinks $P \neq NP$, so they work under that assumption, therefore we have more conditional results with $P \neq NP$ assumption than $P = NP$.</p>

<p>It also helps that in the case of $P = NP$ problems have simpler answers (e.g. it implies that $P = BPP$, etc.) where as there are more possibilities in the case of $P \neq NP$. But that doesn't means we don't have conditional results with $P = NP$. If you want to have a look at how things would look like in that case check what Russell Impagliazzo calls the Algorithmika in his five worlds.</p>

<p>Also check out
<a href="https://cstheory.stackexchange.com/q/1026/">Status of Impagliazzo&#39;s Worlds?</a></p>

<p>Russel gave a talk at IAS workshop on his worlds in 2009 (<a href="http://intractability.cs.princeton.edu//videoplay.html?videofile=cs/IW2009-500kb/Russel%20Impagliazzo.mp4" rel="nofollow noreferrer">video</a>).</p>

CC BY-SA 3.0
2017-05-06T23:51:12.883Z
2017-05-06T23:58:56.297Z
2017-05-06T23:58:56.297Z
Kaveh
<blockquote>
  <p>As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.</p>
</blockquote>

<p>There is a <a href="http://www.scottaaronson.com/blog/?p=2887#comment-1333538" rel="nofollow noreferrer">hidden</a> difference between conjectures equivalent to a $\Pi_1^0$ sentence like Riemann hypothesis and conjectures equivalent to a $\Pi_2^0$ sentence like $P \neq NP$. We sort of already know some algorithms (i.e. <a href="http://www.scholarpedia.org/article/Universal_search" rel="nofollow noreferrer">universal search</a> algorithms like Levin search or Hutter search) which would be polynomial time in case $P = NP$ (well, Levin search only works for syntactic subclasses of <a href="https://en.wikipedia.org/wiki/TFNP" rel="nofollow noreferrer">$F(NP\cap coNP)$=TFNP</a> like <a href="https://en.wikipedia.org/wiki/PPA_(complexity)" rel="nofollow noreferrer">PPA</a> or <a href="https://en.wikipedia.org/wiki/Integer_factorization" rel="nofollow noreferrer">integer factorization</a>, and Hutter search<a href="https://cstheory.stackexchange.com/questions/31838/does-p-poly-neq-np-poly-have-any-interesting-implications/31850#31850"> .</a><a href="https://cstheory.stackexchange.com/revisions/31838/2">..</a>), but that still doesn't settle the $P \neq NP$ conjecture.</p>

<blockquote>
  <p>I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if P=NP was proven to be true, so why is this not assumed?</p>
</blockquote>

<p>You probably mean that we should assume a non-zero probability that $P=NP$, for example by assuming that $P=NP$ with probability 0.01% and $P \neq NP$ with probability 99.99%. Many computer scientists will claim that this is more or less what they do, but they don't see how this assumption should alter what they write in their papers in any substantial way.</p>

<p>What they could do different would be to state the relation between runtimes achieved by reductions between problems more explicitly. But how much more explicit? Should they try to work less with $f(n)=O(g(n))$ and more with $f(n)\sim g(n)$ ($\lim_{n\to\infty}\frac{f(n)}{g(n)}=1$) and $f(n)\lesssim g(n)$ ($\limsup_{n\to\infty}\frac{f(n)}{g(n)}\leq 1$) for stating resource estimates in theorems? The question is just whether this is realistically possible, since even basic tools like the <a href="https://en.wikipedia.org/wiki/Master_theorem" rel="nofollow noreferrer">master theorem</a> are formulated in terms of $f(n)=O(g(n))$, and it is unclear how complicated they would become in terms of $f(n)\lesssim g(n)$ (or whether such a formulation would be useful at all).</p>

CC BY-SA 3.0
2017-05-07T02:18:28.400Z
One of the justifications for big-oh notation in many uniform machine models is that the constants are not robust to the model. For example, see the Linear Speed-up Theorem. (And then I think we still use big-oh in non-uniform models because we're actually using them to try to understand uniform models...)
Joshua Grochow
CC BY-SA 3.0
2017-05-07T19:36:02.410Z
@JoshuaGrochow Even so big-oh notation can [invite misuse](http://chat.stackexchange.com/transcript/message/28480283#28480283), I don't think it needs much justification. It often succinctly expresses exactly what we want to say. I just tried to find similarly succinct notations for situations were we could be more explicit. (When we find ourself referring to the proof instead of the theorem, then this is a typical situation where we probably should be more explicit. This comes up in explanations how constructive/intuitionistic logic can be helpful.)
Thomas Klimpel
CC BY-SA 3.0
2017-01-03T15:05:09.717Z
2017-01-03T15:05:09.717Z
2017-04-13T12:32:28.743Z
Thomas Klimpel
<p>As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.
Other than this, this topic has been discussed at several other places, see <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP" rel="noreferrer">https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP</a> or <a href="https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/" rel="noreferrer">https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/</a>.</p>

<p>Update: Or the very recent Chapter 3 here: <a href="http://www.scottaaronson.com/papers/pnp.pdf" rel="noreferrer">http://www.scottaaronson.com/papers/pnp.pdf</a></p>

CC BY-SA 3.0
2017-01-02T21:17:12.403Z
As much as I like this answer (and I like it a lot), I'm a bit concerned: you can phrase the statement $P = NP$ in several ways. Some examples: $\forall$ languages $L$ we have $L \in P \iff L \in NP$; OR $\exists$ algorithm $A$ s.t. $A$ runs in poly-time and $A$ accepts $w$ iff $w \in SAT$; OR $\forall$ NP-complete languages $L$ we have $L \in P$; OR $\exists$ NP-complete language $L \in P$. Some of these statements start with existential and some with universal quantifiers, so clearly we can't apply your rule (universal quantifier implies probably true) to all of the statements.
Mikhail Rudoy
CC BY-SA 3.0
2017-01-02T22:35:53.420Z
@Mikhail: Indeed! I'm not sure how one could formalize which option to pick.
domotorp
CC BY-SA 3.0
2017-01-02T23:31:12.707Z
@MikhailRudoy: You have to be careful to specify first-order versus second-order quantifiers. When you say "$\forall$ languages $L$" that's a second-order quantifier, but when you say "$\exists$ algorithm $A$" it's a first-order quantifier. So the "$\exists$ algorithm $A$" formulation has *zero* second-order quantifiers, and is thus closer to the true "logical complexity" of the statement "P=NP." As a first-order sentence, this version of "P=NP" indeed begins with an existential quantifier. (Though this doesn't completely resolve your objection, it does resolve your specific examples.)
Joshua Grochow
CC BY-SA 3.0
2017-01-02T23:51:29.990Z
There are many exceptions. Before the monster group was proved to exist, it was a conjecture that started with an existential quantifier. And for one of the Clay problems (the Yang-Mills one), the conjectured outcome starts with an existential quantifier.
Peter Shor 
CC BY-SA 3.0
2017-01-03T00:15:46.433Z
@JoshuaGrochow. If you could explain (or link me to something explaining) what exactly you mean by zeroth-, first-, and second-order quantifiers in this case, that would be super helpful.
Mikhail Rudoy
CC BY-SA 3.0
2017-01-03T16:16:08.747Z
@MikhailRudoy: https://en.wikipedia.org/wiki/Second-order_logic
Joshua Grochow
CC BY-SA 3.0
2017-05-07T00:15:22.463Z
In the simplest form we know of P vs. NP, it is $\Sigma_2^0$. $\Sigma_1^0$ formulas are computably verifiable while $\Pi^1_0$ formulas are computably refutable. If a $\Pi^0_1$ is false it would be computable refutable.
Kaveh
CC BY-SA 3.0
2017-01-02T19:20:50.053Z
2017-01-04T08:46:32.363Z
2017-01-04T08:46:32.363Z
domotorp
<p>Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove $P = NP$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing $P = NP$ as possibly true. However, I often see people working within the framework of it not being true and I was wondering why? It seems more conservative to assume that $P = NP$ in many fields. I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if $P = NP$ was proven to be true, so why is this not assumed? While it is unlikely to be proven either way any time soon, it just seems somewhat odd to rely so heavily on the a conjecture like that. It almost seems paramount to assuming that Goldbach's conjecture is invalid as there is no proof for it either. </p>

CC BY-SA 3.0
2017-01-02T17:27:19.257Z
Goldbach's conjecture isn't the correct analogy. Why do number theorists work under the assumption that the Riemann hypothesis is true?
Peter Shor 
CC BY-SA 3.0
2017-01-02T17:28:34.430Z
@PeterShor That's exactly what I am saying. It tends to be that if something cannot yet be disproved that people err towards the side of acceptance.
Eli Sadoff
CC BY-SA 3.0
2017-01-02T17:30:47.660Z
These aren't random opinions based solely on the fact that nobody has disproved stuff; they're informed opinions. Nobody has disproved the existence of a projective plane of order 12, but nearly everybody thinks it doesn't exist.
Peter Shor 
CC BY-SA 3.0
2017-01-02T17:33:24.080Z
@PeterShor I was not claiming that they are random opinions. Additionally, projective planes exist rather trivially (e.g. the extended Euclidian plane).
Eli Sadoff
CC BY-SA 3.0
2017-01-02T17:33:59.520Z
Oops; typo. I meant to say projective plane of order 12 (corrected now).
Peter Shor 
CC BY-SA 3.0
2017-01-02T17:35:56.667Z
@PeterShor Ah. I think on the whole the Riemann hypothesis is the best comparison when it comes to quintessentiality and doubt.
Eli Sadoff
CC BY-SA 3.0
2017-01-02T17:58:24.850Z
@EliSadoff if you argue otherwise you will be called crazy. Mind that if you want a career would you go against the tide or glide with it. I do not think there is any reason unlike other scientific disciplines. It is a matter of belief by some people who think they have a better chance of knowing the area (in all humility).
Turbo
CC BY-SA 3.0
2017-01-02T18:00:27.267Z
@AJ. That's completely legitimate. I'm not in this field (well not very much at least. I'm a computational scientist so I work with algorithms a fair amount but not enough to delve into P = NP very often), but I was trying to get an explanation. Thanks!
Eli Sadoff
CC BY-SA 3.0
2017-01-02T20:18:15.883Z
@AJ "if you argue otherwise you will be called crazy" ... if you had an *interesting* argument, then it would be far from crazy, in my mind. It would be extremely important. In several cases where researchers have assumed something similar to P=NP, we have been able to derive a contradiction. E.g. the time-space tradeoffs for SAT. (Note: the current question under discussion is not in the ballpark of an interesting argument. It asserts that P=NP is the more conservative assumption, with no reasons given.)
Ryan Williams
CC BY-SA 3.0
2017-01-02T20:22:07.023Z
In a way, if we assume that P=NP, then a large part of the field would be just closed. No more hardness of approximation, explicit constructions, some crypto primitives. If this was true, what other interesting questions could we ask?
Igor Shinkar
CC BY-SA 3.0
2017-01-02T23:46:31.037Z
I don't think OP has seriously done his homework on this question. This is discussed in **many** placed. See for example https://rjlipton.wordpress.com/2009/09/18/why-believe-that-pnp-is-impossible/, http://www.scottaaronson.com/blog/?p=1720, the links Domotor has given, any book on complexity theory..
Sasho Nikolov
CC BY-SA 3.0
2017-01-03T00:57:21.090Z
@SashoNikolov The links you gave a great. As a disclaimer, I am not from the computer science field, but instead from the mathematics field, and was wondering as a matter of TCS principal as to why this was such and the answer was provided to me. I on the whole, albeit rather unfairly, ignore wordpress/blog links because they seem to be less credible, but perhaps I should no longer continue this practice. Thank you!
Eli Sadoff
CC BY-SA 3.0
2017-01-03T11:04:13.870Z
A significant amount of CS is about designing algorithms for concrete problems. Assuming P=NP without knowing the algorithm to prove it is unhelpful for algorithm design. On the other hand assuming P is not equal to NP allows us to move forward with existing algorithms/heuristics while we wait for the truth to be revealed.
Chandra Chekuri
CC BY-SA 3.0
2017-01-03T12:23:48.590Z
@EliSadoff there are several blogs by well-known TCS researchers which are quite reliable. Similarly to how Tao's and Gowers's blogs in math are quite reliable.
Sasho Nikolov
CC BY-SA 3.0
2017-01-03T18:53:16.777Z
@RyanWilliams I just meant there is not that much energy in the community as a whole to take $P=NP$ as a plausibility (just for example look at point #3 [here](http://blog.computationalcomplexity.org/2017/01/predictions-for-2017.html)).
Turbo
CC BY-SA 3.0
2017-01-03T19:21:58.457Z
@ChandraChekuri it is standard exercise to construct a poly-time SAT solver assuming that P=NP
Igor Shinkar
CC BY-SA 3.0
2017-01-04T10:47:03.637Z
@IgorShinkar sure, my point is that it is not helpful as an algorithm that can actually be used. Do you disagree?
Chandra Chekuri
CC BY-SA 3.0
2017-01-14T17:55:46.090Z
@ChandraChekuri I agree. Running over all Turing machines is not very efficient from an algorithmic point of view. Still, there are several examples, where in the beginning there is a polytime algorithm with bad constants, and then it is improved.
Igor Shinkar
<p-vs-np>
Why do computer scientists on the whole work under the assumption that P ≠ NP?
Eli Sadoff
# Why do computer scientists on the whole work under the assumption that P ≠ NP?

(Asked by: username_0 on 2017-01-02)

Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove $P = NP$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing $P = NP$ as possibly true. However, I often see people working within the framework of it not being true and I was wondering why? It seems more conservative to assume that $P = NP$ in many fields. I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if $P = NP$ was proven to be true, so why is this not assumed? While it is unlikely to be proven either way any time soon, it just seems somewhat odd to rely so heavily on the a conjecture like that. It almost seems paramount to assuming that Goldbach's conjecture is invalid as there is no proof for it either.

**Tags:** p-vs-np

> **Comments:**
> **username_1**: Goldbach's conjecture isn't the correct analogy. Why do number theorists work under the assumption that the Riemann hypothesis is true?  
> **username_0**: @PeterShor That's exactly what I am saying. It tends to be that if something cannot yet be disproved that people err towards the side of acceptance.  
> **username_1**: These aren't random opinions based solely on the fact that nobody has disproved stuff; they're informed opinions. Nobody has disproved the existence of a projective plane of order 12, but nearly everybody thinks it doesn't exist.  
> **username_0**: @PeterShor I was not claiming that they are random opinions. Additionally, projective planes exist rather trivially (e.g. the extended Euclidian plane).  
> **username_1**: Oops; typo. I meant to say projective plane of order 12 (corrected now).  
> **username_0**: @PeterShor Ah. I think on the whole the Riemann hypothesis is the best comparison when it comes to quintessentiality and doubt.  
> **username_2**: @EliSadoff if you argue otherwise you will be called crazy. Mind that if you want a career would you go against the tide or glide with it. I do not think there is any reason unlike other scientific disciplines. It is a matter of belief by some people who think they have a better chance of knowing the area (in all humility).  
> **username_0**: @AJ. That's completely legitimate. I'm not in this field (well not very much at least. I'm a computational scientist so I work with algorithms a fair amount but not enough to delve into P = NP very often), but I was trying to get an explanation. Thanks!  
> **username_3**: @AJ "if you argue otherwise you will be called crazy" ... if you had an *interesting* argument, then it would be far from crazy, in my mind. It would be extremely important. In several cases where researchers have assumed something similar to P=NP, we have been able to derive a contradiction. E.g. the time-space tradeoffs for SAT. (Note: the current question under discussion is not in the ballpark of an interesting argument. It asserts that P=NP is the more conservative assumption, with no reasons given.)  
> **username_4**: In a way, if we assume that P=NP, then a large part of the field would be just closed. No more hardness of approximation, explicit constructions, some crypto primitives. If this was true, what other interesting questions could we ask?  
> **username_5**: I don't think OP has seriously done his homework on this question. This is discussed in **many** placed. See for example https://rjlipton.wordpress.com/2009/09/18/why-believe-that-pnp-is-impossible/, http://www.scottaaronson.com/blog/?p=1720, the links Domotor has given, any book on complexity theory..  
> **username_0**: @SashoNikolov The links you gave a great. As a disclaimer, I am not from the computer science field, but instead from the mathematics field, and was wondering as a matter of TCS principal as to why this was such and the answer was provided to me. I on the whole, albeit rather unfairly, ignore wordpress/blog links because they seem to be less credible, but perhaps I should no longer continue this practice. Thank you!  
> **username_6**: A significant amount of CS is about designing algorithms for concrete problems. Assuming P=NP without knowing the algorithm to prove it is unhelpful for algorithm design. On the other hand assuming P is not equal to NP allows us to move forward with existing algorithms/heuristics while we wait for the truth to be revealed.  
> **username_5**: @EliSadoff there are several blogs by well-known TCS researchers which are quite reliable. Similarly to how Tao's and Gowers's blogs in math are quite reliable.  
> **username_2**: @RyanWilliams I just meant there is not that much energy in the community as a whole to take $P=NP$ as a plausibility (just for example look at point #3 [here](http://blog.computationalcomplexity.org/2017/01/predictions-for-2017.html)).  
> **username_4**: @ChandraChekuri it is standard exercise to construct a poly-time SAT solver assuming that P=NP  
> **username_6**: @IgorShinkar sure, my point is that it is not helpful as an algorithm that can actually be used. Do you disagree?  
> **username_4**: @ChandraChekuri I agree. Running over all Turing machines is not very efficient from an algorithmic point of view. Still, there are several examples, where in the beginning there is a polytime algorithm with bad constants, and then it is improved.  

---

## 3 answers

### Answer by username_10 on 2017-01-02. Score: 15 | Accepted answer

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.
Other than this, this topic has been discussed at several other places, see <https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP> or <https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/>.

Update: Or the very recent Chapter 3 here: <http://www.scottaaronson.com/papers/pnp.pdf>

> **Comments:**
> **username_11**: As much as I like this answer (and I like it a lot), I'm a bit concerned: you can phrase the statement $P = NP$ in several ways. Some examples: $\forall$ languages $L$ we have $L \in P \iff L \in NP$; OR $\exists$ algorithm $A$ s.t. $A$ runs in poly-time and $A$ accepts $w$ iff $w \in SAT$; OR $\forall$ NP-complete languages $L$ we have $L \in P$; OR $\exists$ NP-complete language $L \in P$. Some of these statements start with existential and some with universal quantifiers, so clearly we can't apply your rule (universal quantifier implies probably true) to all of the statements.  
> **username_10**: @Mikhail: Indeed! I'm not sure how one could formalize which option to pick.  
> **username_9**: @MikhailRudoy: You have to be careful to specify first-order versus second-order quantifiers. When you say "$\forall$ languages $L$" that's a second-order quantifier, but when you say "$\exists$ algorithm $A$" it's a first-order quantifier. So the "$\exists$ algorithm $A$" formulation has *zero* second-order quantifiers, and is thus closer to the true "logical complexity" of the statement "P=NP." As a first-order sentence, this version of "P=NP" indeed begins with an existential quantifier. (Though this doesn't completely resolve your objection, it does resolve your specific examples.)  
> **username_1**: There are many exceptions. Before the monster group was proved to exist, it was a conjecture that started with an existential quantifier. And for one of the Clay problems (the Yang-Mills one), the conjectured outcome starts with an existential quantifier.  
> **username_11**: @JoshuaGrochow. If you could explain (or link me to something explaining) what exactly you mean by zeroth-, first-, and second-order quantifiers in this case, that would be super helpful.  
> **username_9**: @MikhailRudoy: https://en.wikipedia.org/wiki/Second-order_logic  
> **username_7**: In the simplest form we know of P vs. NP, it is $\Sigma_2^0$. $\Sigma_1^0$ formulas are computably verifiable while $\Pi^1_0$ formulas are computably refutable. If a $\Pi^0_1$ is false it would be computable refutable.  

---

### Answer by username_7 on 2017-05-06. Score: 0

Researchers work under the assumptions they think are more plausible. In the case of complexity theory almost every experts thinks $P \neq NP$, so they work under that assumption, therefore we have more conditional results with $P \neq NP$ assumption than $P = NP$.

It also helps that in the case of $P = NP$ problems have simpler answers (e.g. it implies that $P = BPP$, etc.) where as there are more possibilities in the case of $P \neq NP$. But that doesn't means we don't have conditional results with $P = NP$. If you want to have a look at how things would look like in that case check what Russell Impagliazzo calls the Algorithmika in his five worlds.

Also check out
[Status of Impagliazzo's Worlds?](https://cstheory.stackexchange.com/q/1026/)

Russel gave a talk at IAS workshop on his worlds in 2009 ([video](http://intractability.cs.princeton.edu//videoplay.html?videofile=cs/IW2009-500kb/Russel%20Impagliazzo.mp4)).


---

### Answer by username_8 on 2017-01-03. Score: -1

> As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.

There is a [hidden](http://www.scottaaronson.com/blog/?p=2887#comment-1333538) difference between conjectures equivalent to a $\Pi\_1^0$ sentence like Riemann hypothesis and conjectures equivalent to a $\Pi\_2^0$ sentence like $P \neq NP$. We sort of already know some algorithms (i.e. [universal search](http://www.scholarpedia.org/article/Universal_search) algorithms like Levin search or Hutter search) which would be polynomial time in case $P = NP$ (well, Levin search only works for syntactic subclasses of [$F(NP\cap coNP)$=TFNP](https://en.wikipedia.org/wiki/TFNP) like [PPA](https://en.wikipedia.org/wiki/PPA_(complexity)) or [integer factorization](https://en.wikipedia.org/wiki/Integer_factorization), and Hutter search [.](https://cstheory.stackexchange.com/questions/31838/does-p-poly-neq-np-poly-have-any-interesting-implications/31850#31850)[..](https://cstheory.stackexchange.com/revisions/31838/2)), but that still doesn't settle the $P \neq NP$ conjecture.

> I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if P=NP was proven to be true, so why is this not assumed?

You probably mean that we should assume a non-zero probability that $P=NP$, for example by assuming that $P=NP$ with probability 0.01% and $P \neq NP$ with probability 99.99%. Many computer scientists will claim that this is more or less what they do, but they don't see how this assumption should alter what they write in their papers in any substantial way.

What they could do different would be to state the relation between runtimes achieved by reductions between problems more explicitly. But how much more explicit? Should they try to work less with $f(n)=O(g(n))$ and more with $f(n)\sim g(n)$ ($\lim\_{n\to\infty}\frac{f(n)}{g(n)}=1$) and $f(n)\lesssim g(n)$ ($\limsup\_{n\to\infty}\frac{f(n)}{g(n)}\leq 1$) for stating resource estimates in theorems? The question is just whether this is realistically possible, since even basic tools like the [master theorem](https://en.wikipedia.org/wiki/Master_theorem) are formulated in terms of $f(n)=O(g(n))$, and it is unclear how complicated they would become in terms of $f(n)\lesssim g(n)$ (or whether such a formulation would be useful at all).

> **Comments:**
> **username_9**: One of the justifications for big-oh notation in many uniform machine models is that the constants are not robust to the model. For example, see the Linear Speed-up Theorem. (And then I think we still use big-oh in non-uniform models because we're actually using them to try to understand uniform models...)  
> **username_8**: @JoshuaGrochow Even so big-oh notation can [invite misuse](http://chat.stackexchange.com/transcript/message/28480283#28480283), I don't think it needs much justification. It often succinctly expresses exactly what we want to say. I just tried to find similarly succinct notations for situations were we could be more explicit. (When we find ourself referring to the proof instead of the theorem, then this is a typical situation where we probably should be more explicit. This comes up in explanations how constructive/intuitionistic logic can be helpful.)  

---

