Convex quadratic approximation to binary linear programming

Munapo (2016, American Journal of Operations Research, purports to have a proof that binary linear programming is solvable in polynomial time, and hence that P=NP.

Unsurprisingly, it does not really show this.

Its results are based on a convex quadratic approximation to the problem with a penalty term whose weight $ \mathcal{l}$ needs to be infinitely large for the approximation to recover the true problem.

My questions are the following:

  1. Is this an approximation which already existed in the literature (I rather expect it did)?
  2. Is this approximation useful in practice? For example, could one solve a mixed integer linear programming problem by homotopy continuation, gradually increasing the weight $ \mathcal{l}$ ?

Note: After writing this question I discovered this related question: Time Complexity of Binary Linear Programming . The related question considers a specific binary linear programming problem, but mentions the paper above.

Whether following language is linear or not?

I have a language $ L= \{a^nb^nc^m : n, m \ge 0\}$ .

Now, I wanted to determine whether this language is linear or not.

So, I came up with this grammar:

$ S \rightarrow A\thinspace|\thinspace Sc$

$ A \rightarrow aAb \thinspace | \thinspace \lambda$

I’m pretty sure(not completely however) that this grammar is linear and consequently language too is linear.

Now, when I use pumping lemma of linear languages with $ w$ , $ v$ and $ u$ chosen as follow I find that this language is not linear.

$ w = a^nb^nc^m, \space v = a^k, \space y=c^k$

$ w_0 = a^{n-k}b^nc^{n-k}$

now, $ w_0 \notin L \space (\because n_a \neq n_b)$

So, I’m unable to find whether the language is linear or not and what goes wrong in above logic with either case. Please help.

Help with Linear recurrence relation with balanced partition

In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with “partizione bilanciata” which means “balanced partition”

My course is in Italian and looking online in English I could not find any trace of this method, I know of the recursive tree, induction and master theorem .

Has anyone an idea of how this is called in English ? I don’t like studying in Italian and I do not understand those pdfs.

I’m attaching some images of the formulas.

enter image description here

enter image description here

What exactly “balanced partition” mean, does it have something to do with for example Quick Sort , when you choose a middle pivot and the partitions are equal in size, which means it’s balanced ?

Is it the same as master theorem written maybe in a different way ?

Edit : I can see the form of the recurrence relation is different than master’s theorem.

enter image description here

When for master’s theorem instead of $ c*n^b $ we have $ f(n)$

Thank you

Constant vs linear time given knowledge of input distribution

Question about computer science whether a problem is O(1) or O(N). This was a thought experiment I came up with and I’m sure it’s rather basic. But I wasn’t sure how to look it up so I apologize if this is already posted on here somewhere. But I was wondering … let’s say we have a simple question: given a string of random integers, is there any number that’s greater than a certain threshold value in the series, if that would be a linear or constant time Big O? Now the small twist is that the distribution of the input would be known for example let’s say we want to look at a series of N numbers to see if one is at least N/2. If yes, boom we are done. And let’s say the numbers are positive integers bounded to N so all n < N. Given we know this distribution does it change if it is O(1) or O(N)? If we have a very long string of numbers then of course it is possible that no number meets the threshold but this becomes a much smaller and smaller and smaller possibility for a long series of such random numbers. Does it make a difference if the N/2 threshold is some constant integer value less than N?

Linear programs with strict inequalities and supremum objectives

Linear programming can solve only problems with weak inequalities, such as “maximize $ c x$ such that $ A x \leq b$ “. This makes sense, since problems with strict inequality often do not have a solution. For example “maximize $ x$ such that $ x<5$ ” does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution – the supremum is $ 5$ .

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?

How to detect infinite loop exist in linear bounded automata (LBA)?

The following theorem from Michael Sipser’s book “Introduction to the Theory of Computation” states:

$ A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$ M$ is an LBA that accepts string $ w$ } \}$ .

THEOREM: $ A_{\mathrm{LBA}}$ is decidable.

On the proof part, it states:

The idea for detecting when $ M$ is looping is that as $ M$ computes on $ w$ , it goes from configuration to configuration. If $ M$ ever repeats a configuration, it would go on to repeat this configuration over and over again and thus be in a loop.

I do not understand this: “If $ M$ ever repeats a configuration, it would go on to repeat this configuration over and over again”. What if $ M$ only repeat one configuration, then halts?

Correlation not found ( linear regression) problem

i am new to machine learning i am trying de develop my knowledge and skills with projects, while doing so i encountred a probleme where i didnt find a “well coreleated” varible with the target ,the highest corelation coeffcient i found was 0.44, so i did a scatter plot to determine how the 2 variables are going to behave in order to choose between a polynomial regression model or a linear regression ,so it turned out like this , i am clueless about what to do scatter plot