Hard, harder, hardest — the labels

The vocabulary that separates "expensive but solvable" from "buy the SaaS instead."

1. 01
   An enum is the simplest way to make the labels a thing the codebase carries. Tag each estimation function with its complexity class, and the procurement question — solver, approximation, or SaaS — falls out of the match arm.

   enum Complexity { P, NpComplete, NpHard, CoNp }
   
   fn procurement(problem: Complexity) -> &'static str {
       match problem {
           Complexity::P          => "use the standard library or crate",
           Complexity::NpComplete => "encode and dispatch to a solver",
           Complexity::NpHard     => "approximation or SaaS",
           Complexity::CoNp       => "verifier finds bugs; certifier is the hard half",
       }
   }

2. 02
   & in a type means reference — a borrow of someone else's data instead of an owned copy. A String owns its bytes and can grow. A &str is a view into bytes that live somewhere else — you can read them, you cannot grow them, and they belong to whoever lent them to you. Functions that return strings usually return &str when the bytes already exist somewhere (a string literal, another struct's field) and only return String when fresh bytes have to be allocated.

   let owned:    String = String::from("hello");  // owns its bytes on the heap
   let borrowed: &str   = &owned;                 // a view into owned's bytes
   let literal:  &str   = "hello";                // a view into bytes baked into the binary
   
   // The "&" in a type is "reference to" — a borrow.
   // String  →  owns bytes you can grow or modify.
   // &str    →  read-only view of bytes someone else owns.

3. 03
   'static is a lifetime annotation — a label on the borrow saying how long the referenced data stays valid. The apostrophe prefix marks every lifetime name ('a, 'b, 'static). 'static specifically means "valid for the entire run of the program." String literals like "approximation or SaaS" get 'static for free because the compiler bakes their bytes into the read-only section of the binary — they exist before main runs and after it returns. Most function signatures do not need any lifetime written — the compiler elides (fills in) lifetimes from a small set of rules. 'static is the case where elision cannot help, because the returned reference is not tied to any input, so the lifetime has to be spelled out.

   // Every arm of procurement() returns a string literal.
   // Literals live in the binary forever ⇒ their lifetime is 'static.
   // Rust cannot guess that from the inputs, so we write it explicitly.
   fn procurement(p: Complexity) -> &'static str {
       /* ... */
       "approximation or SaaS"
   }
   
   // Elision in action — no lifetimes written, compiler infers them:
   fn first_word(s: &str) -> &str { /* tied to s's lifetime */ }
   
   // Equivalent with lifetimes explicit:
   fn first_word_explicit<'a>(s: &'a str) -> &'a str { /* same thing */ }
   
   // 'static is the one common annotation that resists elision.
   // The other named lifetimes ('a, 'b, ...) tie a return reference
   // to an input reference and the compiler usually fills them in.