LPs can prove optimality of a result but sometimes this is to expensive and you stop as soon as you reach near optimality based on known bounds.
For several problems you can prove lower and/or upper bounds for the optimal results. For example you can prove that a route between two points may not be shorter than their distance.
If you use LP in production you often don't care about optimality and can work with suboptimal results very well. Worst case you stop after a timeout and just pick the best result.
Edit: I forgot to mention that during solving of a LP you usually get dynamically computed bounds. The branch and bounds algorithm works by computing bounds on relaxed problems that give upper bounds for the original problem.
The biggest problem is heating in winter, which requires way more energy than cooling in summer. So for colder areas doubling Panels will not be enough.
You are right in that there is a class of algorithms for which it is possible to do that. It is just not possible to decide if any algorithm is in that specific class of algorithms or not. There is an even smaller class of algorithms that can be constructed bottom up from halting sub algorithms. But these are not as powerful.
Yeah, just adding, in Rust, there's three main levels:
1. no_std (like no libc + no malloc in C)
2. no_std + alloc (like no libc + malloc in C)
3. std (like a full libc + malloc in C)
The difference between 1 + 2 is like three lines. The difference between 2 + 3 is a change to the entire standard library. ATM only ESP32 devices support option 3 (they build a standard library implementation on top of FreeRTOS/ESP-IDF).
The `core` library is still available on `no_std` and contains a lot of useful stuff, so it’s not exactly like no libc on C. That would be `no_core` which is pretty hardcore (heh). The big things missing in `no_std` are
* file and other I/O, including filesystem ops
* access to system time
* threads
* collections and some other things that require an allocator (not many things actually do in Rust’s stdlib!)
* floating-point functions (the types themselves and builtin operators work fine)
`alloc` gives you `Vec`, `String`, `Box`, `BTreeMap/Set`, ref-counted pointers, and a few `Vec`-derived collections like `VecDeque`. Very annoyingly not `HashSet/Map` though, due to a literally single-line dependence on a system entropy source which happens to not be easily factorable out because reasons.
You don't. It currently requires `-Z build-std=std,panic_abort` and some nightly flags (e.g. `#![feature(restricted_std)]`) but you can build `std` programs on bare metal targets. I can't remember exactly what it does if you try to open files or start threads or whatever (probably panics?) but you can compile and run it. If you don't do any of those things it works fine.
Currently the `sys` crate implementation is hard-coded into the compiler but eventually you will be able to provide it without modifying the compiler so you can e.g. target a RTOS or whatever.
It looks like that work started really recently actually:
You cannot approximate NP-complete functions. If you could approximate them with a practically useful limited error and at most P effort you would have solved P=NP. (disclaimer my computer science classes have been a long time ago)
This isn't correct. What you may be remembering is that some (not all) NP complete problems have limits on how accurately they can be approximated (unless P = NP). But approximation algorithms for NP complete problems form a whole subfield of CS.
Perhaps I'm not using the vocabulary correctly here.
What I mean is, if you ask a human to solve a travelling salesman problem and they find it too hard to solve exactly, they will still be able to come up with a better than average solution. This is what I called approximation (but maybe this is incorrect?).
Hallucination would be to choose a random solution and claim that it's the optimum.
I may be misunderstanding the way LLM practitioners use the word “hallucination,” but I understood it to describe it as something different from the kind of “random” nonsense-word failures that happen, for example, when the temperature is too high [0].
Rather, I thought hallucination, in your example, might be something closer to a grizzled old salesman-map-draftsman’s folk wisdom that sounds like a plausibly optimal mapping strategy to a boss oblivious to the mathematical irreducibility of the problem. Imagining a “fact” that sounds plausible and is rhetorically useful, but that’s never been true and nobody ever said was true.
It’ll still be, like your human in the example, better than average (if “average” means averaged across the universe of all possible answers), and maybe even useful enough to convince the people reading the output, but it will be nonetheless false.
If a driver is tasked with visiting a number of places, they will probably choose a reasonably good route. If the driver claims to have found the optimal route, it may not be true, but it's still not a hallucination and it's still a pretty good route.
The driver certainly cannot be relied on to always find an exact solution to an NP-complete problem. But failure modes matter. For practical purposes, the driver's solution is not simply "false". It's just suboptimal.
If we could get LLMs to fail in a similarly benign way, that would make them far more robust without disproving what the posted paper claims.
Only if you're assuming all questions have binary answers.
For example in the traveling salesman problem you don't have to compute all answers to start converging on an average. A random sampling of solutions can start setting a bounds for average, and your grizzled salesmans guesses would fall somewhere on that plot. If they are statistically better than average then they are far more than good enough. Unless of course you think burning up the observable universe in finding the best solution is the only way to solve the problem of which trip uses the least gas?
True, but FK (in child table) must reference a key (in parent), and most databases won't let you create a key without the underlying index.
The other direction, however, is not a given: most DBs will let you create a FK on fields not covered by an index, so deleting or modifying a parent can benefit if you create such index explicitly, because it can check for the existence of children much faster (and avoid potentially locking the entire table). Again, the access pattern governs what indexes are needed: if you never delete/modify parent, you may not need an index on FK (unless you also have some queries which can use it, of course).
Nobody is arguing that the usecases are the same. In the end you can't even chat with gzip (although you could with it's predictor).
The thing is, that building the predictor is almost the same thing for compression and LLM. Of course the goals and taken tradeoffs are different. The paper shows this analogy.
ChatGPT et al use structured prediction to simulate intelligence. Building the predictor is fancy lossy compression.
Questions arise if lossy compression of things without copyright is legal or not. If I mp3 a lossless recording we currently think it is not legal. With LLMs this is not entirely clear yet.
As it happens I know zip. I ported that to linux back in 0.95 days, I think the code was called info-zip in those days. Chatting with its predictor is a fanciful description to say the least.
I've also read the transformers paper mentioned in the tweet.
Of course an LLM is on some level similar to a compression system, and on some level it's also just high and low voltages on some integrated circuits. Saying "just" glorified compression isn't something I'll believe without good arguments, though.
I have been able to fix these random lags by doing multiple full disk reads. The first one will take very long, because it will trigger these lags. Subsequent ones will be much better.
The leading theory I have read is that maintenance/refreshing on the ssd is not done preventative/correctly by the firmware and you need to trigger it by accessing the data.
For several problems you can prove lower and/or upper bounds for the optimal results. For example you can prove that a route between two points may not be shorter than their distance.
If you use LP in production you often don't care about optimality and can work with suboptimal results very well. Worst case you stop after a timeout and just pick the best result.
Edit: I forgot to mention that during solving of a LP you usually get dynamically computed bounds. The branch and bounds algorithm works by computing bounds on relaxed problems that give upper bounds for the original problem.