You are thinking of trying every possible combination and then checking them sequentially like a deterministic TM would, however a NTM would check all of the possibilities in parallel that is all $m^m$ of them, so you have to polynomial runtime (only the time it takes to check one certificate). For me an easier way to think of non-determinism is that if you choose something, you automatically guess the correct thing, that is the NTM "guesses" the correct path and then verifies it, this makes the polynomial runtime more intuitive.

Just an orthogonal grid; you divide the space into grid cells with size $\Delta x, \Delta y$ and use $i = x/\Delta x,j = y /\Delta y$ as indices into a hash-map. There are some videos about how game developers use it on youtube.

Binary space partitioning and quad trees are options, but they are not trivial to implement. If the points and segments are well distributed I would recommend spatial hash grids, that is dividing the space into buckets, putting the points into the buckets and then look through all points in the buckets a given segment touches. If these buckets are empty one probably has to continue to search radially.

The time hierarchy theorem implies this, there is a proof on wikipedia.

No, but it would prove $NP = coNP$ which is also an unsolved problem. Your question is equivalent to this one.

The argument structure is: Assume there exists a TM that computes $BB(n)$, (the argument), now we have a contradiction. Thus our assumption is wrong. Such a TM cannot exist. Thus $BB(n)$ is non-computable. The TM we chose at the beginning doesn't matter, the only thing relevant is that we assume it computes $BB(n)$ which we use to create a contradiction.

Note that $BB(n)$ is by definition an upper bound on the number of 1s a halting TM with $n$ states can print, so if we find that our TM has $k$ states and can print more than $BB(k)$ 1s and halt, that is a contradiction with the definition of $BB(k)$. So such a machine cannot exist. This then implies that a TM that computes $BB$ cannot exist, hence $BB$ is non-computable.

E.g. let $M_f$ accept any non-regular language like $\{a^{p_n}| n \in \mathbb N\}$ $p_n$ primes, and only fill in all the remaining $a^i$ if $M$ accepts infinitely many words. Note that checking if a word exists such that a TM accepts a word longer than $i$ is in RE.

You applied the masters theorem correctly for $T(n) = T(n/4) + \log(n)$ it implies $T \in \theta(\log(n)^2)$, given ofc. that $T(n) = \theta(1)$ below some bound $n < \kappa$. Make sure that you read the task properly, maybe you missed something.

classic example of a pseudo-poly algorithm would be the dynamic algorithm for the knapsack problem.

@Best_fit The wikipedia definition is perfect: In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

You should look up the $O(n \log (n))$ algorithm for LIS. You will realize that it uses $L[i][k] = $ increasing subsequence of $\langle a_1,...,a_i \rangle$ with length $k$ with the smallest possible last element and some placeholder if no such seq. exists . Using this your def. of OPT(i) becomes easy. Now you just need to find a recursion for $L$.

If you use binary search for each row to determine the index at which $\beta_j > \alpha_i$ the algorithm takes $O((n+m)\log(n))$, but since the $\beta$ and $\alpha$ are ordered, you can use the two-pointer method for that.

I believe that the ordered property might allow for a $O(n+m)$ algorithm. You can discover it by considering two polynomials ($\sum \alpha_i x^i, \sum \beta_j x^j$) with ordered coefficients and drawing a table where the rows are the coefficients of $(\sum \alpha_i x^i) \cdot \beta_j x^j$ (the table columns should be $x^{2n},...,x^0$). Now notice that you can precompute the prefix sums of $\alpha_n,...,\alpha_0,$ and $\beta_n,...,\beta_0$. Notice that the columns will always be made of a subarray of $\alpha$ and a subarray of $\beta$ thus you can use the prefix sums to compute them.