luc4
luc4 on Hacker News
I'm a mathematician and for me math is art :)
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?
To give some nuance on the quote "Experimental evidence + logical deduction can never prove that either the deterministic or the indeterministic view is impossible": We can indeed rule out a local hidden variable model [1].
So if the deterministic view is true, then it has to be a holistic theory. The hidden variables must be global, i.e. "accessible" throughout the universe. They cannot be attached to a particle as in Whittaker's model or Schrödinger's modification.
[1] https://en.wikipedia.org/wiki/CHSH_inequality
Congrats, you just solved P=NP.
We just used the standard ordering < to define the set, it has nothing to do with the candidate well-ordering. If that's confusing, consider the set { 10^-x | x \in N } instead. It also has no minimum element in the standard ordering.
Since the query compilation needs exponential time, I wonder how large the queries can be before jsongrep becomes slower than all the other tools. In that regard, I think the library could benefit from some functionality for query compilation at compile-time.
To give a different opinion, the math topics are actually what I like most. When I'm looking for something on Wikipedia, I want to get a precise definition and related concepts. I don't think it's Wikipedia's job to teach me the material, there's other resources for that.
It seems like the article is missing the central point -- namely that the currency was depreciating monthly, providing an incentive to spend it as quickly as possible.
One could argue that infinite subsets of the natural numbers are not really interesting unless one can succinctly describe which elements are contained in them. And of course there is only a countable number of such sets.
YouTube has a de facto monopoly on long-form video content.
At the risk of stating the obvious, you can criticise the government without personally insulting public officals. In fact, in Germany, you can be prosecuted for insulting anyone; there is nothing special about public officials.
First, these studies merely suggest that microplastics have these effects in humans, yet you state them as fact. However, I don't want to argue that microplastics are harmless or that pollution is not an issue. Neither do I want to defend the point that doubling the population doubles the "speed of discovery". But even if all of your points are accurate, you would still have to show that these negative effects outweigh the benefit of a priori doubling productivity. In fact, you make the even stronger claim that doubling the population will actually cut the "speed of discovery" in half. None of this is substantiated by your argument.
It's ironic that your responses come off as much more rude and condescending than the comment in question.
CICO is fundamentally true, but the point is that "calories-out" depends on so many factors (including "calories-in") that it becomes meaningless.
Yes, exactly. It's missing the monadic bind (which for the list monad would be flatMap).
To be pedantic: Their Maybe class is just a Functor, not a Monad.
I find the videos themselves useful. YouTube just happens to be the place where they're hosted. I support content creators directly and I have a Nebula subscription.
What? We're not refusing to "pay other software companies a few bucks for their engineering work", we refuse to give in to the extortion attempts of a greedy multi-billion dollar company.
I have and will keep financially supporting software I find useful. However, I do agree that it's questionable whether you can easily replace Google as a source of funding.
> Uncomputable functions exist because the halting problem exists.
Uncomputable functions exist because there are only countably many Turing machines. There are problems that stay uncomputable even if the halting problem were computable.
> The class of problems solvable in a finite amount of memory is just the class of regular languages. The “finite memory” is the finite state machine used to solve them.
I think they meant to say "constant memory" since every halting Turing Machine uses finite memory.
Wow, I've seen many AI-powered language apps lately, but this is by far the best. The others, if they offered verbal conversation at all, really struggled with my stuttering while trying to find the right words. I'm impressed that yours doesn't have this problem at all. It even understands when I use technical terms in english.
I'd love if the AI was a bit more fleshed out, so I can actually ask questions without getting the "I'm an LLM by OpenAI..." lecture.
Good question. BB is certainly an upper bound.
Consider the problem P_f of getting an input x and having to compute a value >= f(x), where both the input and the output are encoded in unary. We know that BB grows faster than any computable function, so P_BB cannot be computable.
Suppose for contradiction that there was a computable problem Q with time complexity Omega(BB(x)). This means there exists a Turing Machine M that computes Q and a function T(n), such that for each n there exists an input y of length n, such that M halts after exactly T(n) steps. Moreover, T(n) = Omega(BB(x)).
Then we can construct a Turing Machine M' that computes P_BB. The idea is to run a TM for Q on a length x input and counting the number of computation steps. That number is then larger than BB(n) and thus a valid output for P_BB. Formally:
Let M be a TM that computes Q. Without loss of generality we assume that M uses a binary tape alphabet. Since T(n) = Omega(BB(x)), there exists per definition a C > 0 and an k_0 > 0 such that for all k > k_0 it holds that C*BB(k) <= T(k). M' now operates as follows. Given a unary input x, M' first checks if |x| <= k_0. If yes, M' just outputs BB(|x|). Otherwise, M' enumerates all bitstrings y of length |x|. For each y, M' then runs Q on y step-by-step while incrementing a unary counter c_y. Finally, M' outputs the longest such c_y, divided by C. Per assumption, the longest c_y satisfies C*BB(|x|) <= c_y, so c_y/C >= BB(|x|).
This implies that P_BB is computable, contradicting our initial observation. Consequently, such a Q cannot exist.
In fact, this proof works for any function that grows faster than all computable functions. This means that BB as an upper bound is not tight. For example log(BB) also satisfies this property.
Could you elaborate? The article does.
A larger number of qubits allows us to do effective quantum error correction. The idea is to group multiple physical qubits into one logical qubit, think of it as redundancy.
Crimea was a referendum and Eastern Ukraine separatist rebels. Extent of russian involvement aside, there is a difference between that and an all-out invasion.
> How would that be political suicide?
I'm mostly thinking international politics and -projects like Nord Stream 2. But even internally, there are already anti-establishment movements in Russia. Unpopular military intervention might be grist to the mill for them. I don't think Putin wants to risk a situation like in Belarus a few months ago. It's easier to govern if the people don't openly disapprove of you, even in a dictatorship.
> It's only economical suicide if the West makes it so, which it most probably would not
I remember plans about excluding Russia from SWIFT. I don't know if that is still on the table.
Exactly. Invading Ukraine would be political and economical suicide for Putin and Russia. Yet here we are getting bombarded in the media with the supposed threat of an imminent russian invasion. The chief of the german navy criticises this narrative and is forced to apologize and resign. I don't know but this all feels very dishonest.