[deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP.
And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]
> Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time).
It's a bit more complicated than that, if you want to be careful. Sorting is in both NP and EXP and can be solved in subexponential time.
I think what they proved is that no problem in NP takes exponential time to solve. (Because you can always reduce them to SAT in polynomial time, and then solve SAT in subexponential time.)
EDIT: apparently the runtime bounds they gave here don't survive the usual polynomial reductions, thus they haven't proven that NP != EXP, it seems.
I mean the result that k-SAT cannot be solved in 2^{o(n)} clearly would imply P!=NP, but how does ETH imply NP = EXP? And how does \neg ETH imply NP != EXP?
If I am understanding this correctly (and I am still reading this!) and if this is true, this means NP is sub-exponential. Sub-exponential does not mean P=NP. But yes, this is huge if true.
This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!)
Every paper which assumes ETH is true might now have their conclusions be disproven.
See this from the paper: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems
admit subexponential time algorithms."
It's not clear what you're trying to say or the relevance. The fact remains that "NP is always poly time reduceable to 3SAT" and "3SAT is sub-exponential" does not imply that NP is sub-exponential.
right, but anything linearly reducable to kSAT is trivially sub-exponential, and a discovery like this means that linear reductions are a whole lot more important than they used to be.
Also for NP problems that can't linear reduce to kSAT just having the knowledge that SAT is sub-exponential (and the tools), makes it a lot more likely that we see a whole lot more problems become exponential.
practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.
Your "No" is wrong. As he said, "Conversions to other problems can still end up exponential", so (NP is poly time reduceable to 3SAT + 3SAT is sub-exponential) does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
This defeats a few hypotheses that were widely relied on.
strong exponential time hypothesis, and the titular exponential time hypothesis
It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s).
Assuming P != NP (and that this NP != EXP proof holds up), what's the next most "natural" candidate for how fast NP must grow? This paper appears to show Omega(2^(n/sqrt(log(n))) with a couple additional fudge factors which would be a very disappointing answer.
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Even if all NP problems could be solved in sub-exponential time, it would not imply that NP ≠ EXP. It seems that many people here are confused about what EXP means – it’s the set of all problems that can be solved in at most exponential time, including those in P.
This is not a proof of NP ≠ EXP. NP ≠ EXP would mean that there is a problem that can be solved in exponential time, but not in non-deterministic polynomial time. That’s completely different from what they have shown.
Predictions markets are terrible mechanisms for this, because they require imposing an arbitrary time limit at which point the prediction will pay out. IOW, even if you religiously believed P=NP, but you think it would take at least two years to prove it, you would vote against the prediction if the deadline were one year.
This proves that EXP != NP, which was a stronger claim than P != NP.
In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen.
It is definitely progress towards an answer to P ?= NP.
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
There's a chain of classes P, NP(aka Sigma_1), Sigma_2, .., Sigma_n, ... PSPACE, EXPTIME. What we know for sure is that P < EXPTIME, others are unknown (well, maybe this paper adds something to this, time will tell).
It's conceivable that each of them is smaller than the next, but also that e.g. P < NP = all the sigmas < PSPACE < EXPTIME or many other possibilities. I think the general consensus is that it's more likely that there are more inequalities than not, but the fact is that we can't even show that P is less than PSPACE so far, which would be extraordinarily surprising if it were true.
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
The question is: do the bees see music and art in their structures. I doubt it. One of the defining characteristics of music and art is that they have no obvious direct connection to reproductive fitness.
I’m guessing the price will be at least 8 figures. If you can afford it you can also afford the 20 acre property with the private test track where you can flip your car in front of your friends.
It's not flying, it's brief hops that probably will be geofenced not to be operable on any public roads. I struggle to understand when the operator of the vehicle will ever find a way to use it for any end that isn't "gross negligence followed by totaling the car". It's not even clear it can calculate trajectories in real time to be used at the operator's discretion.
Could be seen as a technology demonstrator for interesting military technology. It could offer something akin to turn based warfare where units charge up and make synchronised moves.
> At most it makes you fall in the water in the correct orientation.
They showed a still of the submarine car from James Bond as inspiration for this.
That's the roadster they should have built. This compressed air jumping thing is impractical and dangerous and will never be road legal. But a submersible car would have actual practical uses, increase survivability in several accident situations and not face the same regulatory hurdles.
If they were actually trying to build something cool I think that would be the play, but everything Elon does now is to bump stock price
Well, maybe not submersible, but if it could even float and move in water it essentially becomes a boat which I don't need to explain is a practical mode of transport.
How many times have you been in traffic waiting to cross a bridge or driving around a body of water wishing you could just go over it?
I used to wonder about the possibility of using thrusters to decelerate for impending crashes. I think for a substantial fraction of accidents that would be enough to massively reduce the risk.. but hopping over is an option I hadn’t considered practical.
Formula 1 cars also have massive amounts of heavily engineered downforce and negative camber to give them insane amounts of grip. Pretty much every street car has enough braking power to lock its brakes in almost every condition but doesn’t have nearly the grip to utilize it.
Not so good on slick roads. Besides, I don’t know of any passenger car or light truck that has insufficient braking performance to the point of the tire grip not being the weak point.
Hopping over a line of cars is only useful if you know there's nothing in front. In an accident this just means a rear end impact becomes an entirely more dangerous accident where one car is falling from the sky onto several more
It doesn't take a lot of imagination to see how being able to jump and hover for 2-3 seconds could be used to avoid otherwise fatal impacts, provided the software was perfect.
Given that we don't have such software, and that this currently requires trading all three seats for compressed gas storage, there are obviously some hurdles to this becoming a practical emergency feature.
I'm not saying it's not cool. Parlor tricks can be very cool, and this one is. But it's still a parlor trick because it's not good for anything other than being cool. When people think of flying cars what they generally have in mind is not a car that can do a flip, it's car that can take them somewhere without needing a road so that it doesn't get stuck in traffic. This car can't do that. All it can do is backflips in a parking lot. That's not nothing, but the novelty will wear off very quickly.
> When people think of flying cars what they generally have in mind is not a car that can do a flip, it's car that can take them somewhere without needing a road so that it doesn't get stuck in traffic. This car can't do that. All it can do is backflips in a parking lot. That's not nothing, but the novelty will wear off very quickly.
Aye.
That said, on previous stories about flying cars I tend to bring up how the helicopter meets such a standard.
Exactly. How did the roadster stick to the curved ramp with no obvious jets firing before going airborne? It wasn't going fast enough for centrifugal force to keep it from falling so how did that part of the magic show work?
Suction as I understand it, it had a ground curtain and the blurb talked about the ability to create downforce to keep the roadster version on the road at high speeds.
The same fans that blew downwards to create lift were likely first run to suck it in to the ramp, then reversed.
These demos were not performed by "daily driver" cars - they were multiple look alike props in a magic show, each optimised for the trick shot and not driver comfort or experience (if any driver(s) even took part).
> The same fans that blew downwards to create lift were likely first run to suck it in to the ramp, then reversed.
That's a nice theory, but it is wrong.
The fans that are used to create suction do not create lift. The amount of air moved by those fans is way too small to create lift, the lift is entirely due to compressed air used as reaction mass.
Fair point, I was thinking the same when I wrote the comment <shrug> .. I still side with the reverse hovercraft sucking force .. and thinking they likely reversed those fans after the need for suction passed (every little bit counts).
I guess nobody clicks on the links anymore? From the OP:
"Our multi-mode fan and ground sealing system acts as a downforce generator, pulling air out from beneath the vehicle. This provides enough suction to hold the vehicle upside down, even when stationary. Powered fans and active wings maximize traction and cornering speeds in all conditions, achieving massive downforce at zero speed. A next-gen steer-by-wire system offers incredible feedback in various road conditions. Activate Track Mode to lower the car and transform the suspension. High downforce or low drag modes can then be used as needed on the track."
Very cool. Too bad the demo was achieved with wires and special effects.
Edit: citation? Common sense. If it was real they'd have done everything they could to prove it. It's as real as Tesla's self driving taxis were a decade ago. How many more times will people get duped by this conman?
I want a citation this was real before I believe literal smoke and mirrors at night.
Didn't F1 cars briefly have downforce fans (basically suction fans underneath the car) until it was ruled out of spec? Basically a "reverse hovercraft" trick, normally used for handling, but "turned up to 11" here.
There was the Brabham BT46 that got quickly banned.
On the front of cars you can actually buy and drive there is the McMurty Spierling an electric single seater with a fan generating more downforce then it weighs (can go upside down)
Yeah it now holds a bunch of lap records on tracks without very long straights (where it looses due to not that high top speed). It also took the Goodwood hillclimb in 2022 and held it for a couple years.
I don't recall the General going vertically upwards. Bo and Luke's motor seemed to lack an engine when "flying" over rivers etc because if it had one, it would have gone vertical quite rapidly (down).
Ballistic means it follows a ballistic trajectory, as in it is governed by gravity and inertia. Flight is typically governed by aerodynamic forces and ballistic trajectories are normally considered undesirable by pilots and passengers alike.
"Ballistic just means that there is no active propulsion."
"Ballistic means it follows a ballistic trajectory, as in it is governed by gravity and inertia."
If we're being pedantic about explicitly not-the-point of my post, drag is an aerodynamic force and included in ballistic calculations. And gliders are not ballistic and are not under active propulsion.
Cool.
Now that we've cleared up that we can both understand definitions, try doing "There's nothing ballistic about laminar flow."
I am having a hard time understanding what you mean by laminar flow. Do you mean, specifically laminar flow over an airfoil, vs turbulent flow? I don’t see how this makes a distinction relevant to ballistics?
I remember reading that there were actually about 25 General Lees. Pretty much every jump totaled one, and they'd swap in another, and haul off the first one to get fixed (or junked).
I'm not even an EV guy, and this is the coolest thing to come out of the automotive space in years. This is almost a throwback to the homologation days of rallying, when automotive companies sold unchained racing cars to the general public because the FIA and WRC deemed it so. Impractical cars in every sense of the word, but phenomenal engineering.
Well the reality is already jesus with a machine gun on a surfing dinosaur, so like there's not much room left to show the crazy version of something to show the principle.
The page talks about a bunch of weight reduction tech, but I didn't see an actual final weight for the Rocket model? Given that it can support itself with "downforce" (and no thrusters, and apparently not much momentum?) at the top of the loop it's got to be pretty light...
It is certainly an engineering accomplishment, but calling it a 'car' is a stretch. Do you believe that this vehicle has a 100kWh battery pack in it? When Tesla demonstrates this vehicle driving two hundred miles on city streets and recharging to repeat the test, I'll gladly change my mind.
Until then, this is simply a purpose built drone, powered by compressed air to perform specific tricks in order to grift and hype up interest in the company.
I can buy a drone from DJI that performs more impressive flying maneuvers than what Tesla showed.
Here’s a 30 minute interview with Tesla VP of engineering looking up close at the battery pack, motor, cooling system. Definitely seems like a real EV to me. They also look up close at the thruster pressure vessel and exhaust system.
That’s not the same vehicle that did the tricks — the “Rocket” version has many downward-facing vents, and presumably a larger tank for pressurised gas and a much smaller battery capable of sustaining the suction but not much more.
It's not a flying car in the way that anyone ever imagined growing up. When people think flying cars they think blade runner or fifth element. Not a car that can jump, interesting as a jumping car may be.
And frankly I'm not sure the engineering is all that impressive. I'm sure someone could've done similar a long time ago, there's just no point to it beyond, well, the parlor trick. Even millionaires have no use for a single seat, road-illegal vehicle with no storage that happens to be able to jump
No, but people will definitely buy the thrust version for the track, if it's ever built. (And assuming most tracks and drag strips even allow using the thrusters, which I doubt.)
Will that be allowed in any multi-person-near-each-other track day? Exhaust that pushes must be very dangerous to be behind if you’re drafting and waiting for the next passing lane.
I recall attending a top fuel drag racing event. One was pop-popping up to the start line. Then the tree turned green, and the driver hit it.
Unfortunately, he had the silly thing in reverse. It launched backwards maybe a hundred feet. The drivers reflexes to shut off the engine were outstanding. If it had gone much further, it would have climbed up one of the full grandstands.
I never stand behind a drag car with the engine running, or in front, or in the plane of rotation of the engine. (I've seen a few engine blowups, and parts often go out sideways.)
Yeah just the same way the rides at amusement parks are that go faster and higher. The end result won't change anything for the rest of us. It's entertainment.
I think I've seen some undergrad capstones also make flying cars that would never actually be produced or sold...
But they lacked a lot of the showmanship here.
You can basically engineer almost anything with enough money for a demo. It's a lot different to engineer something that'll actually get commercialized.
Sometimes I think this sub, being software heavy, downplays the achievements of their own field and overplays the achievements of other fields they lack experience in.
It is a few notches beyond sitting in a wagon and emptying a fire extinguisher to go for a little ride, and about as practical, but I do not see what makes it some incredible feat of engineering.
In what way is this an engineering achievement? Presumably two thousand years ago people understood that flight requires lift. It's not like anything novel is occurring here.
If you want that, Terrafugia has been around for a while - but you still need to drive it to an airport to deply the wings and take off. (Flies for rather more than 3.5 seconds, too :-)
It's a thruster and a fan, in a car made specifically for this stunt, that won't be produced and has all passenger seats occupied by high pressure gas tanks that can do this like once.
Maybe things have changed, but in my day when deploying code to an interplanetary spacecraft, code reviews (emphatically plural) were not optional, and being offended by them would have been a career-ending move.
> More likely just not seen yet, our furthest reaching signals are maybe 50 light years away at best
This is the key. On interstellar scales, things move very, very slowly and you have to plan on time scales measured in millennia. IMHO we are doomed simply because we can barely think beyond the next election cycle. (At least that's true for Americans. The Chinese seem to think in terms of decades and, occasionally, centuries.)
> (At least that's true for Americans. The Chinese seem to think in terms of decades and, occasionally, centuries.)
The Chinese political system is just as short-term-oriented as <insert democracy here> on the whole, and I don't think there has ever been a politician in history who ever thought about workable century-long impacts.
An election taking place every two years doesn't mean that political activity or public perception is structured around a two year cycle. Neither of those things is true.
50,000 years ago (or so) we were a tiny species hanging out in Africa. We didn't think in terms of years, much less decades. This was before we figured out how to measure the length of the year or to predict when the winter would end.
And yet, without any central planning or coordination, we left Africa and colonized Europe, then we headed out across Asia and crossed into the Americas. Plus we sailed from Asia and colonized Polynesia.
Imagine someone saying, "We're doomed because people walk very slowly--it's going to take a thousand years to get to the southern tip of the Americas." And yet, we did.
I think the same thing will happen with space travel and ultimately the colonization of the galaxy.
> Imagine someone saying, "We're doomed because people walk very slowly
I think I may not have made myself clear. The analogy here is not that "we're doomed because people walk slowly". There is nothing that happens here on earth that is even remotely analogous to the constraints that the speed of light imposes on interstellar processes. Even at a leisurely walking pace, a human can circumnavigate the planet in less time than it takes light to reach the nearest star. Human walking speed is blindingly fast (relative to the size of the planet) compared to the speed of light (relative to the distances between stars).
The reason we're doomed is not that we're not walking fast enough, it's because we won't stop walking and take time to think about where we should be going. We just go.
> a human can circumnavigate the planet in less time than it takes light to reach the nearest star
I was surprised by this, but the math checks out (assuming you mean the nearest star other than the sun of course). The circumference of the Earth is about 40000km, at a leisurely pace that's 10000 hours or about 400 days. Proxima Centauri is about four light years away, so the walker has plenty of time for sleep and sight seeing.
But my point is, "we just go" is exactly how we conquered the Earth. We didn't think, "let's colonize the whole planet!", we just went. We walked from Africa all the way to the tip of South America.
We weren't doomed then and we're not doomed now. We will colonize the solar system and eventually the galaxy.*
* Assuming past performance is indicative of future performance.
> Assuming past performance is indicative of future performance.
Yeah, well, there's yer problem right there. We will not colonize the solar system, and certainly not the galaxy, because we haven't figured out how to stabilize the situation here on earth. Yes, we colonized the planet, but for most of the history our lack of planning was compensated by technological limitations and limits imposed by the laws of physics. Those are mostly gone now, and I'll be a little surprised if civilization doesn't collapse before the end of my life (and I'm in my 60s). I would be very surprised if it lasts to the end of the century, though of course I won't be around to see that.
> But my point is, "we just go" is exactly how we conquered the Earth. We didn't think, "let's colonize the whole planet!", we just went
And not even all of us said that. The majority may have even stayed just a small group probably said “we’re going to check out what’s beyond that hill”.
Spreading out all over the world isn't particularly special. Flies, rats and roaches did as well, for instance, so spreading all over the world is not necessarily a sign of cosmic manifest destiny.
That's not the point. It's not walking, it's planning. When all you have are rocks and spears it doesn't matter how far you can plan. When you have nukes and other people's lives in your hands, it does matter. Like, any of the recent wars. What kind of planning went into those stalemates? Evidently none. What about inflation? Still unsolved? Undoing all the green energy efforts made in the past? Well done, apes of Africa, well done.
We also have a tendency to repeat the same mistakes over and over again throughout history, even learning and forgetting cures to diseases, which makes me believe that the duration of our lifespans is a significant limiting factor.
A too-large portion of the population is incapable of learning from something that didn't happen to themselves directly, a smaller subset will even outright deny the existence of things that don't happen to them. Another half the population still believes in ghosts.
I don't understand how your name could not have been carried along on the cap table all these years. In my experience when I've made an investment in an early stage company and they have a liquidity event, they come looking for me.
Private pilot here. No, I'm quite sure very few of you here would have made the same mistake as evidenced by the fact that literally hundreds of thousands of aircraft land successfully every day, many of them under much more adverse conditions. This is not a oh-it-could-have-happened-to-anyone kind of screwup, this is a did-this-guy-really-go-through-basic-pilot-training kind of screwup.
I’m not a manned pilot, but have my part 107 and have spent a few thousand hours flying combat flight sims - ~150kts in a cargo aircraft, four seconds from departing the runway, seems like the worst possible time to abort a touch-and-go. Then consider the numerous automated audio warnings and the copilot suggesting a go-around, and it seems pretty ridiculous to me.
Don’t get me wrong - if I had to land that plane, I’d likely have overrun the runway too. I’m not saying it’s easy, only that it appears to me that they were operating well outside the documented parameters that are the pilot’s responsibility to know.
I just looked it up, and a 767’s Vref is 122-165kts, with Vref at max weight at 144kts. They touched down at 158kts, nose down. The approach was ~35kts over speed, they were above the glide slope, and not bleeding speed fast enough to sink - so they dropped the nose.
From what I can see, they were screwed the moment they touched down - the last moment they had a reasonable opportunity to abort was when they decided to drop the nose and commit instead.
They could have “aborted” at almost any time prior to when they did. And even that may have been fine if they had stuck with it.
A decent rule of thumb in aviation (and life…) is that you’re allowed to change your mind once. Waffling kills more people than switching to a bad decision does.
I have a strong hunch there a deeper more human/emotional component involved. Like Pilot A was not in the right mental headspace. A bad breakup? Some other kind of personal loss? Or an urgency of a personal kind?
Those are a few situations when a trained individual could make a series of bad decisions. More so if they were forced into the situation (flying) despite raising objections. It has happened to other 21 Air pilots in the past - when they objected to flying but were forced, so who knows?
Absolutely does not absolve this individual of the incident. It’s a burden they’ll have to bear for the rest of their lives. But it could help explain why?
They made a series of at least ten (and that's kind of charitable) this-must-never-happen mistakes that likely rise to the level of extraordinary criminal negligence, including ignoring checklists, alarms, configuring the plane for landing in general, and basically everything related to safety.
You don't have to extend sympathy, just as you don't have to extend sympathy to drunk drivers who kill people.
I am not a pilot and I don't know anything about flying. I can go along with the idea that the pilot / crew made mistakes. So the next obvious question is how do we make sure this does not happen again?
I am not a pilot nor do I know aviation but I sincerely doubt the air traffic controller on duty has the mental capacity to babysit each and every plane that is departing and arriving second guessing each and every decision they make. I don't know if they even have access to all the data the pilots have and even if they did I don't know if they can make decisions on time. I mean the way I see it the ATC will coordinate with grounds crew to make sure a plane can land/crash land as safely as possible even if it has no engines, wheels, or even flaps. I don't know how but I know they will try their best to coordinate everyone the best they can.
I mean, complete ethical nihilism is one way to try to avoid losing this particular argument, but I don't think you'll get many people to agree with you on it.
You're being downvoted because actual qualified aviators are telling you how egregious of a mistake this looks to be, and you're quibbling with them without any professional credibility on the subject.
In any aviation incident, it’s generally a good idea to wait for the full NTSB report before drawing any firm conclusions.
That said, it is exceedingly difficult to find any explanation for what happened in this case that doesn’t boil down to incompetence or gross negligence.
There were so many opportunities to avoid this accident. The crew seemingly more or less single-handedly punched a hole straight through the entire Swiss cheese model. It’s so bad it’s hard to imagine they weren’t drunk at the controls.
This is honestly one of the few cases where it looks so blatantly and obviously negligent that I'm comfortable commenting ahead of the investigation results.
Even in a case where someone has drilled themselves into a mountainside, there's value in trying to see things like "were they distracted? Was there mechanical failure? Did they have a freak medical emergency and get incapacitated? Did unexpected weather crop up?" And in other cases, it's a "but for the grace of God go I" moment where you understand how they could have made the wrong decision in good faith. Even years out of the cockpit, I'm willing to give most aviators the benefit of the doubt, because God knows I screwed up enough in my day.
But the only thing I can think of that compares to this level of negligence was the F/A-18 pilot 20 or so years ago who lost his wings after booming his non-towered hometown airport at over 500 knots and below 500 feet with absolutely zero pre-authorization or waiver from the FAA for that kind of thing.
reply