texts: High-level requirements for a Proof of "Saving to the Database"

texts:
This question is about a few sentence description of what a proof would look like (and technologies / logics involved) for a complex api call through many layers. Trying to get a sense of the techniques and key points to watch out for. I understand it would take a lot of work.

In learning about formal proof and verification, I've come across Operational Semantics, Hoare Logic, and Matching Reachability Logic. All of them are pretty low-level and describe how to prove stuff such as a while loop with a few assignment / arithmetic operations, but that's it.

I am wondering what the general / high-level requirements are to prove something like "saving a record through some https API to the database", where it goes through the network (https) and through a bunch of servers finally arriving at an array of replicated databases like MySQL.

In unit testing, you would simply write a test that the method (let's say save()) creates the record. You would make a database query and see if the record matched the record you thought it would be.

I am wondering what it would entail to write a proof of this (at a high level, just a few sentence description is all). What things would need to be proven. If you can't write a proof, then what if you still wanted to at least partially prove the system's correctness. What it would take.

It seems like you could write a Hoare Logic statement such as:

{P}
save({ type: 'asdf', foo: 'bar', a: 'b' })
{fetch('asdf', 'latest') == { type: 'asdf', foo: 'bar', a: 'b' }}

That's at least better than nothing. But I'm not sure if you can write a proof with just that.

Then to know that it actually was in the database and not in some cache in the browser, you would have to know that fetch had a proof that it went through the network to some API, and that API request went to the database, and the database did whatever. That's basically what I'm wondering, if creating a proof for save starts off with the Hoare Logic statement like above, and then progressively you add more detail to the proof. In this way it's almost developed like via TDD. At some point, then, I'm wondering when you could say "it is proven".


texts: LR(1) parsing, problem with look ahead symbols

texts:
I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution.

I'm trying to fill the LR(1) parsing table for the grammar below:

S->xAz
S->BAx
A->Ay
A->e
B->yB
B->y

Ι don't have to extend the grammar since S does not appear in any right hand side of any rule.

First(A)=y,e
First(Ax)=x,y
First(B)=y
First(Ay)=y

Lookahead symbols in brackets.

So,
I0 = Closure(S->.xAz($) , S->.BAx($) ) =

S->.xAz($)
S->.BAx($)
B->.yB(x,y)
B->.y(x,y)

When i try GOTO(0,x) i think that i should go to:

S->x.Az($)
A->.Ay(z)
A->. (z)

To find the lookahead symbol for A->. & A->.Ay i take First(z). But the official book solution says the lookeahead is (z,y).
Where does that y comes from?

Thank you in advance!


texts: Let $A = \{ uu \text{ } | \text{ } u \in \{a,b\}^* \}$ be a language. Suppose that we want to prove that A is not regular via the pumping lemma, why is the string w = $a^{p} a^{p}$ not valid to derive a contradiction?


texts: Inferring reward function and transition model from optimal policy

texts:
Consider an MDP where the transition model and the reward function are unknown.
Consider an optimal policy $\pi^*$ generated from this MDP (say by some oracle who does know the transition model and reward function).
How can one infer the reward function and transition model from an optimal policy? For such a question, there may be multiple approaches, so this question is mostly a reference request.


texts:
Input: undirected graph $G$, starting node $j$ for Justin Bieber (JB), and starting nodes for 4 fans $f_1, f_2, f_3, f_4$.

This problem has turns: for every turn, JB can either stay at his current node or move 1 node adjacent. Fans are working together and follow the same rules, but can share the same node. The fans are trying to occupy the same node as JB, and if any one of them achieves this, JB loses (Yes, you are on Justin's side for this problem!).

If both JB and his fans always have knowledge of the locations of everyone else, decide if it's possible for JB to avoid his fans indefinitely, no matter what his fans' strategies are. Your pseudo-code algorithm must be bound by a polynom in graph size $n+m = |V|+|E|$

This was a tricky, original problem from our algorithms class I'm really interested in. I was thinking that one way JB could avoid all the fans was if the graph was laid out in a way so that he and all his fans would go in a cycle forever, with JB at the front. But we weren't given the strategies for the fans though, so I'm just assuming they move in whatever direction that brings them closer to JB's location (but could there be a more complicated strategy they use, like box him in somehow?) I'm thinking for the pseudo code it should somehow decide whether JB and his fans can make such a cycle, but any help would be greatly appreciated.


texts: How do compilers implement symbolic (rather than textual) insertion?

texts:
From a programming language designer's point of view, how is "symbolic"
insertion implemented as opposed to "textual" insertion using pre-processor
macros?

I understand the basics of how "textual" insertion works in C and C++. That is,
the pre-processor might transform:

#include "person.hpp"

class employee
{
    person p;
};

into:

#ifndef PERSON_HPP
#define PERSON_HPP

class person
{
public:
    uint32_t height_;
};

#endif // PERSON_HPP

class employee
{
    person p;
};

This is required because the size of the employee class can only be determined
if the compiler knows the size of the person class. One disadvantage of this is
slow compilation speed. A program consisting of a single source code file
main.cpp might have thousands of lines inserted into it by the pre-processor
before compilation begins. This can be avoided in some cases by forward
declaring the class and using pointers. The employee class cannot use the
person class until it is defined, (which is why the implementation file will
still include "person.h") but it does remove header file dependencies and
increases compilation speed.

class person;

class employee
{
    person* p;
};

For a language like Java, on the other hand, no textual insertion is required.
Instead, "symbolic" insertion is performed. So the file below would not be
"fleshed out" with the definitions of the dependent software modules.

import com.example.library.person;

class employee {
    private person p;
};

I can't wrap my head around how the compiler accomplishes this. I imagine that
because Java is garbage collected, it doesn't need to know the size before it
is declared, in much the same way as classes can be forward declared in C++
without including the entire file. But how does the compiler know that
p->some_function_that_does_not_exist(23) is valid?

This question was originally asked on stack overflow.


texts: Does every computational problem have a decision version?

texts:
Is the following claim correct?:

  Every computational problem has a decision version of roughly equal computational difficulty.

If the above claim is correct, please give a reference for it.

(I find this pdf from Prof. E. Demaine, but he doesn't provide any references.)


texts: Getting the flit size in a Tiled Chip Multicore Processor(TCMP) system with a mesh architecture

texts: Consider a TCMP system with, say, a 4x4 mesh Network on Chip (NoC) where each tile has a superscalar processor. It is given that that the TCMP uses 64-bit words and the inter-router link bandwidth is 128 bits. So, the size of each flit passing through this network would be equal to 64 bits or 128 bits? I know that flits are the basic units of transfer between a pair of routers. Then would their size be equal to the bandwidth or the word size?


texts: In which paper is written that you can transform one problem to another to show NP-completeness?

texts:
For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard:
Post

I am searching for a scientific paper to cite where it is written, that this is a valid method.

Does anybody knows one?


texts: Get $n^{\mathrm{th}}$ element of sorted subset sums

texts:
I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums).
Attempt at solving :
I have been looking at ordering the sums starting with the unbounded knapsack problem (UKP) with equal weights to find the sets of each size with minimal sum, then establishing a rule for determining the order of corresponding sets after replacing elements, in the hope that this would reduce the number of comparisons. However, this doesn't seem to simplify the problem.


texts: If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?

texts:
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$,
$Y$ is polynomial-time reducible to $Z$?
If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$?
True, false or we don't know? Why?


texts: Recursive definition for the length of a string?

texts:
I found a couple of answers online but I don't quite understand why the answer is right:

The length of a string is:
If a string has no characters, then its length is 0.
Otherwise, the length of the string is 1 + length of the tail


texts: Did I correctly prune this min-max search tree using alpha-beta pruning?

texts: I am studying some old past test questions.  Is this search tree correctly pruned?


texts:
We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input.

The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$
that minimizes $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right).$$

For example, take $n = 3$, $a_1 = 10, a_2 = 1, a_3 = 100, b_1 = 10, b_2 = 100$, and $b_3 = 1$.
  If we take $O$ so that $O(1) = 1, O(2) = 3$, and $O(3) = 2$, we have $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 1311.$$

The desired output is $O(1) = 3, O(2) = 1$, and $O(3) = 2$, which yields $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 321.$$

Trying all possibility is exponential.
How can I find an optimal permutation $O$?


texts: Why is Graph Isomorphism downward self reducible?

texts:
To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing an oracle that solves graph isomorphism for (n-1) vertices.

To be clear, the oracle only tells 'Yes' or 'No'. It does not give us the isomorphism.

This problem appears as an exercise in Arora-Barak's chapter on Interactive Proofs.

How do I show that Graph Isomorphism is downward self-reducible?

My attempt is to start with an arbitrary vertex in $G_1$ and guess its image in $G_2$, and remove them and make an oracle call on the remaining graph. But now, I do not know how to proceed. These graphs being isomorphic may not necessarily mean that the original graphs are isomorphic.


texts: Many of us are familiar with the $P$ class. Counting solutions is believed to be a difficult task and that is why we usually end up approximating the number of solutions (we relax the accuracy of the counting). I want to ask, if relaxing the quality of the solutions counted has been addressed as a problem. Is there for example, any algorithms able to answer the question: How many vertex covers there are, with 3 times the cardinality of the minimum vertex cover? Is the problem $P-$ complete?


texts: Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?

texts:
Let an infinite language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ?

I've understood that the answer is: it depends on what exactly $L$ is.

So basically I'm trying to think of two scenarios for $L$ - one which $L\in R$ and one which $L\in RE \setminus R$, but haven't come up with something useful so far.

I'd be glad for help.


texts: Example of unrestricted grammar which produces non-context-sensitive language

texts:
I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$.

I can not find any example of real unrestricted grammar which produces a non-context-sensitive language (of words). While there are examples of non-context-sensitive languages like here or here, there are not examples with proper grammars for them. Could somebody provide such example?

(Ideally if you would provide links to corresponding papers where such example(s) are described).

Note: I've tried to build unrestricted grammar for known universal Turing machines, as it was suggested in commentaries above. I've used JFLAP tool for this purposes. But obtained grammars appear to be extremely huge, incomprehensible and complex. If you would use same approach and give clear explanation of result, this would partially suit me. Thanks.


texts: Computational complexity of calculating mean vs median?

texts:
Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions).

I am curious which is more computationally intensive to calculate, the mean or the median?

Naively, I would suppose calculating the mean involves summing up the $N$ numbers and then dividing by $N$, hence it has linear $O(N)$ complexity.

Computing the median would need to perform some sort of sorting algorithm, https://en.wikipedia.org/wiki/Sorting_algorithm, it seems the best algorithm performs at $O(n\log n)$ complexity.

Hence, for general $N$, it is more computationally intensive to calculate median? Is my reasoning correct?

Thanks for any help.


texts: BCNF Decomposition: Confusion regarding given answer

texts:
I encountered the following question:

Given a relation R(A, B, C, D) with the following functional dependencies:
A -> B, C -> D, B -> C.

The BCNF Decomposition of R is:

A) {(A,B), (C,D), (B,C)}
B) {(A,B), (C,D), (A,C)}
C) {(B,C), (A,D), (A,B)}
D) All of the above

According to my understanding the solution should be D) ALL of the above.
This is because for each schema, the condition for BCNF holds as given by this link: http://www.cs.sfu.ca/CourseCentral/354/jpei/slides/UsingBCNF-3NF.pdf
      (Page 18)

The other two do not preserve some dependencies but in BCNF decomposition it may happen that the dependencies are not preserved.

However, the answer is given as (A). Please can someone explain? Thanks.


texts:
On page 53 or CLRS it has said :

  We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions
  $$\begin{align}
 O(g(n,m)) = \{  f(n,m)  : &\text{there exist positive constants }c,
 n_0,\text{  and } m_0 \\
   &\text{ such that } 0 \le  f(n,m) \le cg(n,m)\\
   &\text{ for all } n\ge n_0\text{ or } m \ge m_0 \}
\end{align}$$

I think this definition has a problem cause if  $n \ge n_0$ for some constant $n$ then we don't need to grow $m$! I feel something is Wrong! It must be the word "and" instead of "or" for example :
$f(x , y ) = x^2 + y^2$
$g_2(x,y) = x^2 + y$
$g_1(x,y) = x^2 + x*y$

by the definition $f(x,y)$ is $O(g_1(x,y))$ !
or even $f(x,y)$ is $O(g_2(x,y))$ ?

please guide me .


texts: Suppose I have a script (.vbs, for example) that is stored in a file. How does the code in the file get converted into machine instructions?  What is between the vbs file and the processor?


texts: Voronoi diagram algorithm with non-euclidean metric

texts:
Do you know any easy to implement algorithm for constructing a Voronoi diagram from a given set of points on a surface, using some different metric (taxicab, for instance)?
It can be some modification of Fortune's algorithm.


texts:
I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number of times in relation to whether a particular loop can be executed in parallel. The following is a text from one of the thesis:

  The theory concerning loop analyses and transformations is unified in a well known mathematical framework called the polytope model. However, it's applicability is limited to array-based scientific applications exhibiting explicit linearity.

As far as my knowledge (which is limited) is concerned, i think it has to do something with the memory accesses and loop bounds . I am not from a CS background and hence don't have much theoretical knowledge, if this is a topic taught in a typical CS class. If not i would like to know what is it, i am just not able to get a hang of it.

If anyone can provide a detailed explanation that would be good or any resources where i can learn about this, that would also do great.

P.S : I am happy to make any further editions or add details which may be require to answer it better.


texts:
Let $f$ be a binary relation defined on set $S$, which contains numbers from $1$ to $n$. It is also given that number of $|\text{Img}(f)| \le k$. I want to store the function $f$ such in way such that space required is minimum.

I am trying to store the function with a graph, but number of edges turnout to quadratic in $n$.

Question :  How to store the relation $f$ space efficiently?


texts: Transitive reductions of transitive closure

texts:
Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure C of A?
For example the connectivity of nodes in both graphs would still be the same.
For example, we can connect all nodes in A to their minimal elements (smallest subsets) in A and remove all other edges, leading to B.


texts:
A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$.

A subset $M \subseteq E(H)$ is a matching if every pair of edges from $M$ has an empty intersection.

The dual $H^*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\{e_1, e_2, \cdots , e_m\}$ and whose edges are given by $X = \{X_1, X_2, \cdots, X_n\}$ where $X_j = \{e_i | v_j \in e_i \}$, that is $X_j$ is the collection of all edges containing $v_j$.

My question: Is maximum matching problem equivalent to maximum independent set problem in its dual graph?
Are both NP-hard and cannot be approximated to a constant factor in polynomial time (unless P = NP)?

Thank you!


texts: What runtime complexity if DNF formula not PAC-learnable, $O(2^N)$ or $O(2^{2^N})$ runtime?

texts:
Valiant's theory of PAC learning looks at the tradeoff between expected error and algorithm runtime in different classes of learning problems.  In particular, a lot of his analysis focuses on which classes of disjunctive normal form (DNF) formulae are learnable in polynomial time while minimizing expected error (PAC learnable).

However, many classes of DNF formulae are not PAC learnable.  This means that learning takes an exponential amount of time based on the number of variables $N$ in the formula, i.e. the algorithm runtime is $O(2^N)$.

I assume that the DNF formula that is learned in this case is not the minimal DNF formula, since it is NP-Hard to do so, meaning the complexity is $O(2^{2^N})$.

If so, then this is confusing to me.

Say there are $2^{10}-5$ samples from $f$, and the algorithm has to predict the remaining 5 bits.  If my understanding of PAC learning is correct, there is an algorithm that should be able to accurately predict the 5 bits in $O(2^N)$ time.

However, it also seems to me that to accurately predict the 5 bits the algorithm has to figure out which of the $2^{5}$ different ways of filling in the bits has the shortest DNF formula, due to Occam's razor.  But, if the algorithm has to figure out the shortest DNF formula in each of the $2^5$ permutations, then it has to perform logic minimization, which has a runtime of $O(2^{2^N})$.  Then, that means that if a DNF formula is not PAC learnable, its runtime is super-exponential, not exponential.

So, which is it?  Does a DNF being not PAC learnable mean the algorithm's runtime is $O(2^N)$ or $O(2^{2^N})$?


texts:
I am perpetually confused when it comes to static scoping and dynamic scoping and their differences and Wikipedia isn't of any help, so here's my question:

Given the following pseudo code in a hypothetical programming environment, what are the outputs under the following conditions?

call by need using static scope
call by name using dynamic scope

global int n = 100, m = 5;
void fun(x){
    int n = 10;
    print(x + 10);
    n = 200;
    m = 20;
    print(x);
}
main(){
    fun(n + m);
}

Additionally, what would be two environments where I can run this code to check the output with the conditions? C uses lexical scope, but it does not support call by need while Bash supports dynamic scope, I guess!


texts: Hindley-Milner system with let expansion

texts:
I'm reading these slides that present Hindley-Milner type inference. In the system HM, we have the following let rule:

$\dfrac{\Gamma \vdash t:S \;\; \Gamma,x:S \vdash t':T }{\Gamma \vdash \text{let} \, x = t \, \text{in} \, t':T}$

Here $S$ is a type scheme, i.e $S ::= S | \forall a. S$, which allows polymophism only on let expressions. Then, the following let rule is proposed for a system HM':

$\dfrac{\Gamma \vdash t:T \;\; \Gamma \vdash [t|x]t':U }{\Gamma \vdash \text{let} \, x = t \, \text{in} \, t':U}$

so all the occurrences of the binding are replaced and the result needs to be type checked. There is a theorem relating the two approaches:

$\Gamma \vdash_{HM} t:S \iff \Gamma \vdash_{HM'} t: S$

and as a consequence the following corollary is established:

  Let $t^*$ be the result of expanding all let's in $t$ according to the rule. $let \, x = t \, \text{in} \, t' \to [t|x]t'$. Then, $\Gamma \vdash_{HM} t:T \implies \Gamma \vdash_{F_1} t^*: T$. Furthermore, if every let-bound name is used at least once, we also have the reverse $\Gamma \vdash_{F_1} t^*: T \implies \Gamma \vdash_{HM} t:T $.

Here $F_1$ is the simply-typed lambda-calculus.

I would like to gain some intuition on why this reverse direction holds. How does a let-bound name that is not used affect typing? Any reference is also appreciated.


texts:
MAX-3-CUT gets a graph and a number $k$, and determines whether three sets of vertices can be found within that graph, where at least $k$ edges are in the cut.
We define the cut as all edges $(u,v)$ where $u$ and $v$ are in a different set.

MAX-CUT also gets a graph and a number $k$, and does the same but by dividing it to two sets of vertices.

It is known that MAX-CUT is NP complete and I'm trying to show that MAX-3-CUT is also NP Complete by reducing from MAX-CUT.

What I've done so far:

Showing that MAX-3-CUT in NP is easy using a verifier.
I think the reduction should be, given $\langle G=(V,E),k \rangle$ return $\langle G',k+|V| \rangle$,
where $G'=(V'=V+{w}, E'=E+\{(w,v) : v \in V\})$.
Proof of correctness:
doing so, It's easy to show that if $\langle G,K \rangle$ is in MAX-CUT then $\langle G',k+|V| \rangle$ is in MAX-3-CUT by setting the third group to be $\{w\}$.
The problem is I can't do the opposite direction: if $\langle G,k \rangle$ isn't in MAX-CUT than $\langle G',k+|V| \rangle$ isn't in MAX-3-CUT.
I also tried to show that if $\langle G',k' \rangle$ is in MAX-3-CUT then $\langle G,k \rangle$ is in MAX-CUT but I get stuck with how to turn 3 sets into 2.

Note: I was able to show that MAX-3-CUT is NPC by reducing from 3COL (pretty straightforward), but I need it to be reduced from MAX-CUT.


texts: I've been around some research articles which talks about Contextual Algorithms. I want to know what is a contextual algorithm in computing in general.


texts: Does throughput includes CPU idle time also?

texts:
I have 3 processes P1,P2,P3 having gantt chart as follows =>

Now, CPU remains idle in 0 - 2 sec and 44 - 47 seconds as I/O is taking place.

Does, this affect throughput as 3 processes can be completed in total 47 sec .

Hence, throughput = 3 / 47 .

Is this correct or am i missing something ?


texts: Turing Machine with additional finite memory of size $n$

texts:
The question itself:

Let us define a generalization of Turing Machines to include a finite memory of >size $n$.
We denote such
a Turing Machine formally as:
$M_{mem} = (Q, Σ, γ, δ_{mem}, n, q_0, q_a, q_r)$
where all the definitions are identical to the standard Turing Machine except >that there is the finite memory size n and the transition function δmem. At each >step, the transition depends on the
current state, the input on the tape and all the memory. The transition to the >next step can update
the entire memory.
Formally: $δ_{mem} : Q × Γ × Γ^n → Q × Γ × Γ^n × {L, R}$.
Given a finite memory Turing Machine $M_{mem}$, define $formally$ a (standard) Turing Machine $M$ such
that $L(M) = L(M_{mem})$. Namely, both Turing Machines accept the same language.

my approach
I am asked to give two different constructions of such a turing machine. The first way that I managed to come up with is to encode the memory into the states of the turing machine and I managed to do so. I thought that a second way to do it is to encode the memory into the tape itself by concating the string in the memory into the input char itself but this causes problems because the turing machine doesn't have access to the memory in such a way because it will write down the encoding and then move left or right so it won't see the encoding of the memory no more. please guide me with the second approach and/or suggest me another way to do it.


texts: Proof that no O(n) multiplication algorithm exists

texts: For the multiplication of two $n$ digit numbers, the best known algorithm has complexity $O(n \log n)$. Has it been proven that this is the best possible, or that an algorithm $O(n)$ is not possible?


texts:
I have a homework that I should find the formula and the order of $T(n)$ given by

$$T(1) = 1 \qquad\qquad
  T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.
$$

I've established that $T(n) = \frac{1}{n}$ but now I am a little confused. Is $T(n) \in O(\frac{1}{n})$ the correct answer for the second part?

Based on definition of big-O we have that

$$O(g(n)) = \{f(n) \mid \exists c, n_0>0\text{ s.t. } 0\leq f(n) \leq cg(n)\text{ for all } n\geq n_0\}\,.$$

This holds for $f(n) = g(n) = \frac{1}{n}$ so, based on the definition, $O(\frac{1}{n})$ should be correct but, in the real world it's impossible that algorithm can be faster than $O(1)$.


texts: Algorithm for determining if a statement is a paradox

texts:
Please bear with me, since I have just started working on this.

Assuming that the laws of thought apply.

The basic goal of the algorithm is to recast the statement into true or false premises and check if a true and false clashes. If there is a clash then the statement or the set of statements is/contains a paradox. This is the rule for determining if a statement or a set of statements is/contains a paradox.

When I say clash, it means that a statement upon recasting cannot be said to have both true and false attributes.

Rule 1:

"This statement is true" is true.
"This statement is false" is true.

The set of both statements is a paradoxical set.

Rule 2:

If in a statement there is a clash between true and false statements then it is a paradoxical statement.

"This statement is false" is true

Russell’s paradox:

"R, which is the set of all sets which are not members of themselves, is a member of itself" is True
"R is a set of all sets which are not members of themselves" is true.
"R is a set of all sets which are members of themselves" is false.
"R is a member of itself" is true.
Collectively it cannot be true, because there is a clash.

Now, we only need to recast the statement into true and false using the "not" operator to evaluate if a statement is true or false. We can evaluate all truth values and find if there is a clash between a true and false somewhere. If there is a clash then the collective set of statements or the statement is a paradox.

I got a couple in there. Can anyone throw me a paradox where this fails? I am trying to make it even simpler. Thank you so much! I think you will need some logic to recast more complicated statements, but this should identify the simple ones.

If nothing else, could you please verify this to be correct, and let me know if there is any procedure for finding if a set of statements contains a paradox currently exists. I think the general procedure detailing a clash between true and false in a paradox is absolutely correct.

I just came to know that there is a boolean procedure for finding self reference paradoxes, but it seems to me that my method might just be slightly more efficient, since it does not require solving for the entire set of statements but can halt whenever a clash is found. It could be hard to find if the set of statements has a solution or a clash or not, in the case of Wen's paper on the same, which recasts statements as boolean statements.

I can use this to disprove strong AI. Can someone please tell me if it is already proven that a human like intelligence cannot be recreated on a Turing machine.


texts: If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

texts:
I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-complete, can I say that A is NP-complete too?
Actually, I would say yes, because if I can convert a problem that I don't know how to solve to one that I know, then that problem must be at least as hard as the reducible one. So, A should be NPC.
However, I got to another idea that I can convert an easier problem to a hard one, so I could say that A is NP, but I couldn't guarantee that it's NPC.
Which ideia is correct?


texts:
I was reading up on the four color theorem and am wondering if there is any practical application of it. (I dont think seperating the map into four different colors can be considered an application.)

I tried Googling for applications but couldn't find any.


texts: Choosing a random edge with restrictions

texts:
Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|U|}$ ,or $v \in V$ w.p $\frac{1}{|V|}$.
2. There exists a polynomial time oracle, which can, given $u \in U$ (or $v \in V$), returns the degree of $u$ (the degree may be exponential in $n$).
3. The size of $E$ is unknown.
4. One can not test, given $u$ and $v$, if there is an edge between $u$ and $v$.
5. There is an oracle which can, given $u$, return $v$ such that $v$ uniformly chosen from the set of all neighbors of $u$.

If one has only polynomial time (in $n$) - is it possible to choose an edge uniformly at random? Is it possible to choose from a distribution close to uniform?

Without these restrictions, it would have been possible to choose $u$ w.p $\frac{deg(u)}{\sum deg(u)}$, and then choose $v$ u.a.r from the neighbors of $u$.


texts: How to solve if we have $3^{(n-2)/2}$ in recurrence relation?

texts: In a question i found the recurrence relation $a_n=a_{n-2}+3^{(n-2)/2}$  then i should solve this relation with using generating factor but $3^{(n-2)/2}$ makes difficult to solve . Is there a solution for such a relations ?  Or is my answer  wrong ?


texts: Are type abstraction values and universal types not for non functions, but only for functions?

texts:
In Types and Programming Languages by Pierce, Chapter 23 Universal Types has a summary of System F in the following figure, in particular, "type abstraction values" and their types "universal types".

In all the examples I have seen so far in the chapter, in particular Section 23.4 Examples, (not sure if I miss any example):

all the type abstraction values are parametrically polymorphic functions, by allowing the types of their arguments to have any type, and
all the universal types, i.e. the types of type abstraction values, are types of parametrically polymorphic functions.

Are type abstraction values and their universal types not for  non functions, but only for  functions?

More specifically, in any type abstraction value, say $\lambda X.t$, must $t$ have a function type, not a non-function type?

In Section 23.4 Examples, values of base types and of recursive types  are type abstraction values, because their definitions in the section are   functions by Church encodings.

Thanks.


texts:
Given two problems A and B.

Given two algorithms a' and b'. a' solves A and b' solves B.

If A reduces to B and B reduces to A.

Then can we say anything about a' and b'? Are they the same?


texts: Algorithm for undirected projective dependency parsing

texts:
I am looking for an algorithm that will get an optimal projective undirected dependency parse.

That is, given the sentence 'Mary does love John', and an edge-weight function $f$ (that is, a function from pairs of words in the sentence to real numbers), like

  $f$(Mary,does)  = 1

  $f$(Mary,love)  = 5

  $f$(Mary,John)  = 2

  $f$(does,love)  = 2

  $f$(does,John)  = 3

  $f$(love,John)  = 5

I want an algorithm that will give the edges of the maximum projective spanning tree as:
{(Mary,love), (does,love), (love,John)} with a total weight of 12.  That is, it should give this:

Crucially, the algorithm shouldn't give {(Mary,love), (does,John), (love,John)}, even though it has a higher weight of 13, because in that case the dependencies are not projective (the arcs (Mary,love), (does,John) cross each other). That is, it should not give this:

Equivalently, I am asking: what algorithms exist for finding a Minimum/Maximum Spanning Tree on an ordered graph, such that the resulting structure is projective?  A bit more formally: given a totally ordered set of nodes $(S,<)$, and a edge weight function $W: S × S → ℝ$,  is there a good algorithm for finding the optimal-weight spanning tree over this set of nodes, such that the resulting structure has the property that every sub-tree is contiguous in the ordering (for any subtree $T$, for all $t,s$ in $T$ there is no $r$ not in $T$ such that $t<r<s$)?

Without the projectivity requirement, any classic MST algorithm will do (such as Prim's, or Kruskal's).
With the projectivity requirement, but for directed graphs/dependencies Eisner's algorithm (a faster version of Arc-factored Projective Parsing) is standard for getting the optimal directed projective dependency parse.

I am looking for a (probably CYK-like) algorithm like Eisner's, but which will work on undirected dependency parsing. That is, an algorithm for finding the maximum projective spanning tree for undirected ordered graphs.  Or, perhaps, a proof that Eisner's algorithm will with some modification to work on undirected graphs will be guaranteed to give the optimal projective spanning tree.


texts: Prooving equations are non derivable in Sigma algebra

texts:
Let Σ be the signature made up from the following symbols.

e: 0 arguments function (constant symbol)

f: 2 arguments function

g: 1 argument function

Variable set Var is made up from x,y,z

Let E be the set of the following equations

f(x,f(y,z)) = f(f(x,y),z)

f(x,e) = x

f(g(x),x) = e

Can someone explain to be me how I can prove that the following equations are non-derivable from E

f(e,x) = x

f(x,g(x)) = e


texts:
I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious about how it can be shown that DFS visits all the nodes.
I also googled for it. But it seems that every lecturer do some copy-paste work from this book in their pdf's, so I couldn't find anything useful.
By DFS we had to show that it found the shortest path. But since DFS does not calculate something like that I have no idea how to prove it.

Off the topic, why are those proofs so important? Throughout the book there are so many lemmas and theorems which can be really boring sometimes. I understand how an algorithm works in 10 minutes, perhaps need another 5 to 10 minutes to understand how to analyse the running time, but then I'm loosing 1 hour just for some useless lemmas. Besides, and worse even, I studied almost 50 proofs/lemmas of different algorithms till now, I never managed to solve one of them by myself. How can I gain the "proving ability"? Is there a systematical way to learn that? I don't mean the Hoare logic way with invariants, rather the informal way described in the book "Introduction to Algorithms". Is there any book which focuses on "how to prove algorithms" and show that in a systematical, introductory way ?


texts: How to schedule events optimally given when the events are available?

texts:
Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example:

$$
\begin{align}
\textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\
\textrm{Event 2} &\rightarrow \textrm{[2, 4]} \\
\textrm{Event 3} &\rightarrow \textrm{[4]} \\
\textrm{Event 4} &\rightarrow \textrm{[2, 3]}
\end{align}
$$

How would I go about generating a schedule so that the events are scheduled optimally? For the example above, one possible optimal schedule would be:

$$
\begin{align}
\textrm{Period 1} &\rightarrow \textrm{Event 1} \\
\textrm{Period 2} &\rightarrow \textrm{Event 2} \\
\textrm{Period 3} &\rightarrow \textrm{Event 4} \\
\textrm{Period 4} &\rightarrow \textrm{Event 3} \\
\end{align}
$$

Is there any way to do this in better than checking every permutation? This seems like the reverse of the graph-coloring problem for scheduling, so is there any way to construct a graph to encapsulate this relationship and maybe find a shortest path? Can someone point me in the right direction on how to approach this?


texts: Encroaching lists as a measure of presortedness: is it really one?

texts:
Encroaching Lists as a Measure of Presortedness is the title of a 1988 paper by Skiena that describes the concept of encroaching lists, how to generate them from a sequence, how they can be used as a measure of presortedness $Enc$, and then describes the Melsort sorting algorithm, which is adaptative with regard to $Enc$.

Basically, given a sequence, one can build a sequence of encroaching lists: for every element in the original sequence, compare it to the head of the first encroaching list and add it to the front of it if it's not greater than the head, otherwise compare it to the tail of the first encroaching list, and add it to the end of that list if the element in greater than the tail. If the element is neither smaller than the head or greater than the tail, try with the next encroaching list, etc... eventually, if it doesn't match any existing encroaching list, create a new one and add the element in.

This description is a bit rough, so here is an easier example (1): the sequence $\{6, 7, 1, 8, 2, 5, 9, 3, 4\}$ will result into three encroaching lists: $\{1, 6, 7, 8, 9\}$, $\{2, 5\}$ and $\{3, 4\}$.

Skiena asserts that the number of encroaching lists can be used as a measure of presortedness; another paper even shows as an example that $Enc(\{6, 7, 1, 8, 2, 5, 9, 3, 4\}) = 3$.

However the paper Right invariant metrics and measures of presortedness by Estivill-Castro, Mannila and Wood formally define measures of presortedness, and one of the main definitions (2) is the following (let $X$ be a sequence and $M$ a measure of presortedness):

  If $X$ is in ascending order, $M(X) = 0$.

If we follow the logic of the previous example (1), $Enc(\{0, 1, 2, 3, 4, 5, 6\}) = 1$ because there is only one resulting encroaching list containing the full sorted sequence. However, if $Enc$ as described was a measure of presortedness, then we should have $Enc(\{0, 1, 2, 3, 4, 5, 6\}) = 0$ per the given definition (2).

So, shouldn't $Enc$ instead correspond to the number of encroaching lists generated from a sequence minus one in order to be a proper measure of presortedness? I can't find more details about that in any paper.


texts: Algorithms of placing N weighted balls into M uniform bins while striving for balanced weight?

texts:
Suppose there're $N$ weighted balls and $M$ equal weight bins, it's guaranteed at least one placement exists that all the balls can be placed into bins.

What's the right algorithm to achieve a well-balanced placement where each bin has almost equal weights of balls?

I know if the bins are of different weights, the problem is NP-hard; Not sure a simplified question can be solved in linear time.

I'd appreciate any references where I could find some papers discussing the complexity and solutions related. Thank you!


texts: Can a method be written if the language is undecidable?

texts:
If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and false otherwise.

If a language is undecidable, what does that mean? Does it mean:

a.) We cannot write a method; we cannot even conceive of a method.

b.) We can write a method that returns true for each string that is an element of the language; for strings that are not an element of the language, the method may return false or it may loop indefinitely.

c.) Other (what?)


texts: Feasible to apply image "interlacing" concept to video streaming for smoother buffering?

texts:
The current state of video buffering technology is to encode a video multiple times at different resolutions, then when your network speed changes you change which video you are buffering from.

Would it be possible to give this same user experience but implement something like the interlacing method used in PNGs or in progressive JPGs (Adam7 algorithm or similar) to make this work more efficiently?

The basic concept would be that the video is encoded once, at its highest possible quality. Then as your network speed changes you can only download a certain percent of a frame each second. Since the data would be interlaced you would see a lower quality frame from not having enough bandwidth to download it all in a timely fashion.

This would be particularly interesting to see used in video calls so that the video can't stutter, just get worse in quality.


texts:
I have found this tool:

https://www.tools4noobs.com/online_tools/string_similarity/

and it says that is based on the article:

"An O(ND) Difference Algorithm and its Variations"

available on: http://www.xmailserver.org/diff2.pdf

I have read the article, but I have some doubts about how they programmed that tool, for example the authors said that it is based on the C library GNU diff and analyze.c; maybe it refers to this:

https://www.gnu.org/software/diffutils/

and this: https://github.com/masukomi/dwdiff-annotated/blob/master/src/diff/analyze.c

The problem that I have is how to understand the relation of that software tool with the article. For what I read it shows an algorithm for finding the LCS (longest common subsequence) between a pair of strings, so they use a modification of the dynamic programming algorithm used for solving this problem. The modification is the use of the shortest path algorithm to find the LCS that has the minimum number of modifications.

At this point, how they use that theory to find the percentage of similarity between a couple of strings. I know that, for example, the Leveshestein distance can use dynamic programming for knowing the number of edits to transform one string to another; which is something quite similar that they do in the article. Nevertheless, what is the relationship between the LCS and string similarity?

Also they use a threshold of 0.4 in the software took that I do not know for what it is. Anyway, where did I get lost? Any help, please.


texts: How regression is used in item-based collaborative filtering?

texts: In the paper "Item-Based Collaborative Filtering Recommendation Algorithms" In section 3.2.2 about regression, it is said the the user's actual rating of item N (Ru,n),  is replaced with an estimate of that rating (R'u,n) via linear regression. The linear regression model seems to be mapping rating of the target item (i) to ratings of the similar item which the user has also rated (N). Question is, what is input into the linear regression model for the estimate (R'u,n) to be calculated. It can not be the target user's rating of the target item (Ru,i) since that is what we are trying to predict in the first place. Is the input into the regression the target user's rating of the similar item (Ru,n)?


texts: Word Frequency with Ordering in O(n) Complexity

texts:
During an interview for a Java developer position, I was asked the following:

  Write a function that takes two params:

  a String representing a text document and
  an integer providing the number of items to return.

  Implement the function such that it returns a list of Strings ordered by word frequency, the most frequently occurring word first. Your solution should run in $O(n)$ time where $n$ is the number of characters in the document.

The following is what I answered (in pseudocode), it is not $O(n)$ but rather $O(n \log n)$ time because of the sort. I cannot figure out how to do it $O(n)$ time.

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Does someone know or can someone give me some hints?


texts: Term for most degenerate tree with two children on every inner node

texts:
I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf.

(Image from Penn State course STAT 557, Data Mining, lesson 10.)


texts: Reducing optimization problem to its decision version

texts:
There are two problems that need to be solved. Both problems use a compatibility matrix $C$, where $C[a, b]$ is how compatible students $a$ and $b$ are.

(1) Given an $n \times n$ compatibility matrix $C$ for $n$ students, and $r$ rooms with sizes $s_1, s_2, \dots, s_r$, where $n$ is the sum of room sizes, and a target $A$; determine if there is some assignment of the students to the rooms with average compatibility value at least $A$.

(2) Given an $n \times n$ compatibility matrix $C$ for $n$ students, and $r$ rooms with sizes $s_1, s_2, \dots, s_r$, where $n$ is the sum of room sizes; find an optimal assignment of the students to the rooms.

These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For both problems, you find an efficient program on the Internet that solves that problem. Unfortunately your budget will only allow you to buy one such program.

Assume that you have a program that solves the second problem in time $\Theta(n^j)$, for $j ≥ 1$. Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm?
Assume that you have a program that solves the first problem in time $\Theta(n^k)$, for $k ≥ 1$. Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm

I understand how to do problem 15, but for problem 16, I have no idea.


texts: High dimensional Pareto dominance query data structure

texts:
I have a large (10 million+) set $X$ of  data points in some high dimensional $\mathbb{R}^d$ ($d \geq 500$) space. Each data point is quite sparse, e.g. has around $10$ components. Every missing component can be seen as having value $-\infty$ for the purposes of this problem. Associated with each data point $X_i$ is a price $y_i$.
As a quick refresher, a Pareto order is a partial order that orders vectors by those that are 'strictly better', component-wise. That is, for $a, b \in \mathbb{R}^d$ we have
$$a \preceq b \iff \forall i  : a_i \leq b_i.$$
In this case we also say that $b$ dominates $a$ (although not strictly, $a$ and $b$ could be equal). Finally note that this is very much a partial order, it very often happens that $a$ and $b$ are incomparable.
Let $D(z) = \{x \in X : z \preceq x\}$ be the elements in our dataset that dominate $z$ (taking into account only the data points, not their associated prices). I wish to know if there exists an efficient data structure that can answer two things about some $z \in \mathbb{R}^d$  (even sparser, e.g. around $4$ to $5$ components):

the number of items that dominate $z$, or $|D(z)|$, and
the cheapest $k$ prices among those that dominate $z$, or the smallest $k$ elements of $\{y_i : X_i \in D(z)\}$.

Note that $k$ is small here (e.g. $10$) even though $D(z)$ might contain thousands of elements.

Does a data structure solving this problem efficiently exist? Every approach I can think of suffers badly from the curse of dimensionality.


texts: How to implement a faceted search efficiently

texts:
I know Solr and the likes are able to provide faceted search out-of-the-box. But how is faceted search actually implemented technically?

How are those engines able to efficiently search for items based on a dynamic list of attributes given by a query and to provide pagination at the same time?

Definition : https://en.wikipedia.org/wiki/Faceted_search .. even Wikipedia does not list down the technical details


texts: Is a problem in NP if it is decided by some non-deterministic, polynomial time turing machine?

texts:
I am working trough the book "Introduction to the theory of computation", 3rd edition, by M. Sipser. On page 294, the book states:

  A problem is in NP iff it is decided by some non-deterministic,
  polynomial time turing machine.

I get that it is decidable by some NDPTTM if the problem is in NP, the other way around I do not quite get.This is because I feel like all problems in $CoNP-NP$ can also be decided by some Non Deterministic polynomial time turing machine. I have the following solution in mind: Lets assume $P \neq NP \land NP \neq CoNP$. Take a problem $A \in NP - CoNP$. Now there is problem $\overline{A}$, which is in $CoNP$. Lets say NDTM $N$ decides $A$ in polynomial time. Now we modify $N$ by replacing every reject with accept and every accept with reject. We now have a polynomial NDTM $N'$ which decides $\overline{A}$ in poly time. According to the theorem proposed by the book, this should imply that $\overline{A}$ is in $NP$, but it is not.

Am I missing something here?

Edit:

So, I have seen the possible duplicates and I learned a lot: I see now that $N'$ does not necessarily decide $\overline{A}$. I Do still believe my question is subtly different, so here I go:

Take problem $B \in CoNP-NP$. There is a NDTM which decides $B$ in poly time, right? So, according to the theorem, $B$ should be in NP.

I firmly believe the book is correct, but does that mean that $B$ cannot be decided by any NDTM in poly time?


texts: Which m numbers in the range [1, k] have sum equal to n

texts:
Given the values of $n, k, m$, you have to check if there are $m$ distinct numbers in the range from 1 to $k$ have the sum $n$ or not ?

$n$ represents the required sum
$k$ represents numbers range(1,2,3,... to k).
$m$ is the number of elements in the range from 1 to $k$ that has the sum $n$.

Example: n = 12, k = 8, m = 3 ==> there are 3 numbers in the range from 1 to 8 that have the sum 12 which are 2,3,7.

The problem is taken from hackerrank and called bonetrousle.


texts: Finding median of 2 sorted arrays in O(log n)

texts:
If there are given two arrays, A and B, each containing n real numbers in sorted order. How to compute the median of all the numbers in A and B, in O(log n) time. I have to make an algorithm that takes at most logarithmic time.

My idea:

A = 1, 3, 6, 8, 10, 15, 20

B = 1, 2, 3, 7, 10, 30

C = sort(A, B)

a = len(A) // 7
b = len(B) // 6
M = (a+b)/2 // 6.5
if M is a fraction:
    Median = C[M+0.5]
else:
    Median = (C[M]+C[M+1])/2

How to write sort function under complexity O(log n)?
I don't even have to sort all the elements of A and B, I only need the first M+1 elements of C because of above method.


texts: Unsplittable flow in capacitated networks

texts:
I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be routed without capacity violations.

This problem seemed to be similar the classical unsplittable flow problem (UFP). However, I am not really interested in routing as many flows as possible. I rather want a solution where all flows are routed without violations or I will recompute different demands and try again.

Since this is just part of a bigger heuristic I am building, I was looking for fast and easy to understand algorithms that I could implement. I read some papers and presentations on the UFP (e.g. this). Unfortunately, in the algorithm description (slide 22) it doesn't descirbe how the possible paths are searched for and how the flow is routed.

I would be thankful for some fast and simple algorithms to solve my problem. If the UFP is not as similar as I thought, I am also glad to learn about new more applicable problem models.

I also thought about calculating the shortest paths using Dijkstra's algorithm while also updating the capacities. But that might not always find solutions, even if it is a feasible problem, i.e. when the order of the routed flows is of matter. Also, I'm not sure if this is a very efficient way.


texts: Separating two strings without a separating character

texts:
Say you need to write a function such that you have string a and string b.
The function argument is a concatenation of string a and string b.
The function prints string a and string b separately. I'll explain.

For example one can think of a naive solution such that 'x' will be a separator character and so if we want to print "hello world" for example we create a function that prints everything as string a until it encounters an 'x' char and than it knows that string b is starting.
So our argument will be something like:

void separateString("helloxworld");

But this eliminates the option of using 'x' as a char in our String.

I am sure that there is a simple solution to this that I am not getting.

Not looking for code, just your idea. The code will be easy to implement.

Thanks


texts:
When a process inside a monitor with Mesa semantics finishes, another process can acquire the monitor. Now there can be starvation here when there is a thread with a lower priority.

Are there monitors of Mesa-semantics type that don't cause starvation and thus have bounded waiting?


texts: Is 'double max-$k$ vertex-cover' NP-hard?

texts:
Consider the following problem, which I have called '$\mathsf{\text{double max $k$-vertex-cover}}$':

  Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ has a size of at least $t$?

Is this problem NP-hard?

I suspect it is, since the similar problem of max $k$-vertex cover is NP-hard. The same trick for that problem, setting $t=|E|$, does not apply here, as that gives the trivial answer of $|V|-\#\text{zero-degree vertices}$ (in other words, double max vertex-cover is a trivial problem).

Unfortunately, I have been unable to find a reduction. This question seems related, but does not solve this problem for the same reason a reduction from minimum vertex cover fails. (A generalisation of this problem to set covering would look similar to that question)

Background: I encountered this problem in an attempt to show NP-hardness of another problem in this answer, but I think this problem is interesting on its own.


texts: Feeding real-time data and binary search algorithm termination

texts:
This question was asked in our exam long a go and I don't remember exact words.

The scenario was,
Initially you are given a set of finite data to start with, and a key value (which you have to find in a given set). Can we terminate binary search algorithm/program, if we grow the size of the data by feeding new finite data in different quantum during the search is going on.

e.g. if I am searching name of a person in a directory, and there is a on-going survey of the new connections by telecom dept., which they are transmitting in database from remote location continuously (without interruption) and those newly found data are fed in binary-search in real time.

Can we say that binary search will terminate for the key value in this scenario before new data is fed?, if yes then how to prove it?

Sorry, if I am not clear enough. I will try to explain further if required.


texts:
This is a question from the book Algorithms by Jeff Erickson.

Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A[i .. j] or a suffix followed by a prefix A[i .. n] · A[1 .. j]. Describe and analyze an algorithm that finds a contiguous subarray of A with the largest sum.
The input array consists of real numbers.

My approach:

There are two possibilities

1.) No Wrapping around (We can use Kadane's Algorithm)

2.) Wrapping around(ie; Starting index of the subarray is greater than the ending index) (I have doubt in this case)

Now return the maximum of two cases as result.

For the second case, searching on the internet provided an approach without proof.

The approach is to find the subarray with minimum sum and subtract it from the sum of the entire array (ie; sum(A) - min_subarray_sum(A)). How is this solution correct?

Link for the method used in the second case: https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/


texts:
There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are identical (- belong to the same pair) or different (- belong to different pairs). What is the best way to sort the socks in matching pairs?

The obvious algorithm is: grab a sock, scan the pile for its matching sock, and put that pair aside. This algorithm requires time $O(n^2)$.

I Found a related question, On the complexity of sock-matching from about 10 years ago, which also describes an $O(n^2)$ algorithm.

If each sock has a numeric ID, or another ordinal property, such as: wavelength of color, then the entire set of socks can be sorted by that ordinal property in time $O(n log n)$, and then the pairs can just be collected with an $O(n)$ scan. But, in this question I assume that there is no order on the socks - we can only tell whether two socks are identical or different.

In a similar question in StackOverflow (How to pair socks from a pile efficiently?), the accepted answer suggests to use a hash, but again, this assumes that each sock can be represented by a set of properties such as color, pattern, etc., so that each property can be handled separately. In this question I assume that the properties of the socks are only accessible via a function that tells whether two socks are identical or different.

There is a paper named Sock sorting, which initially seems related, but actually it deals with another problem, where two socks might seem identical although they are different (this probably makes the problem more difficult).

So, my question is: assuming we only have a binary "identical/different" relation on the socks, can we match the socks faster than $O(n^2)$?


texts: Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

texts:
There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching results that are computed or fetched from some storage increases memory use but avoids repeating the same time-consuming task. Compressing arbitrary data without information loss tends to take longer the closer you want to get to its implicit limit for entropy.

But besides that, trade-offs seem to occur throughout almost every level of computing: the theory behind algorithms and data structures, hardware, programming, all the way up to project management. I'm wondering if there's some fundamental principle underlying this that makes trade-offs inescapable.

For specific cases I can see why trade-offs exist. Data structures could in abstraction be seen as cached versions of some algorithm's execution. The work is done up-front and the result kept in memory, with the trade-off being some overhead for managing the structure. A hashmap allows fast lookup by a key (constant time) rather than having to traverse all elements in a collection (linear time) because the "look-up" work has been done up-front when adding something to the map. Purely functional data structures supply some insight in the relation between data structures and algorithms. But for a CPU cache, for example, I don't know why the cache can't be made as big as the RAM memory and as fast as a typical cache; is it physical constraints, or simply cost? And regardless of which it is, why does the trade-off exist?

So my question is whether these various trade-offs seen in computing are simply analogues and the trade-offs in memory use/computing time and those in cache size/speed are the same things in different guises, or if they're distinct things. And if various trade-offs are distinct cases, is there some fundamental, deeper reason why trade-offs exist? Is there some reason why something always has to give in one place in order to receive in another? Is it some basic aspect of information theory, of physics? And are there cases where we can "have our cake and eat it" and optimize everything?

Sorry if the question comes across a bit as philosophical, but I've found it's hard to research something if you don't first have the right name for it. And in information theory some problems turn out to be variations of one another, or can be reduced to some fundamental concept (e.g. computability/Turing machine).


texts: The content of an implication from the snm-Theorem

texts:
I have a question on the statement of the s-m-n Theorem and the implication
$$
 \varphi_{f(x,y)} = \lambda z \varphi_x(\varphi_y(z))
$$
for some recursive function $f(x,y)$ cited in the above link. In what sense does this follows from the s-m-n theorem and in what sense does it gives anything new?

To be more specific. As I see it to apply the s-n-m-theorem the function on the right side must be partial recursive or computable, but $\varphi_x(\varphi_y(z))$ is just the composition of computable functions (by the universal turing machine theorem $(y,z) \mapsto \varphi_y(z)$ and so on are computable). But knowing this already says that it has some Gödel coding, and the fact that this is effective (and total) is given by the typical proofs that the composition of computable functions is computable (i.e. by giving an algorithm to construct a suitable Turing machine). So the statement that there exists some recursive $f(x,y)$ gives nothing new to what I know from the basic proof that the composition of computable functions is computable?

So have I missed anything? Or in what sense does this follow from the snm-theorem? And does it states anything nontrivial?


texts: Turing machine that converts decimal to binary

texts:
I'm a beginner in Turing machine computation and want to design two TMs; one that converts decimal number to binary, and other one that converts binary to decimal.

Could anyone help me design these Turing machines? How can I start?

Thanks.


texts: Is there a specific problem that is in both NP and co-NP but not in P?

texts:
A problem is in NP if a correct answer to it can be verified to be so in polynomial time.

A problem is in co-NP if an incorrect answer to it can be verified to be so in polynomial time.

P is a subset of the intersection of the sets NP and co-NP.

My question is: what is a specific problem that is in the intersection of co-NP & NP, but is not in P?


texts: Can someone explain what is the reason for thread-pooling in Linux, even if the threads are light to create and destroy??


texts:
I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$.

Something that comes very close to my goal is a block cipher, say AES. But block ciphers have fixed block size (e.g. 64, 128 bits), and I want something with parameterizable (and smaller) "block size" $\log_2 |X|$. I also don't need many characteristics of block ciphers (e.g. $k$ secrecy, etc.), only the permutation part.

Something else that is quite close is the Lehmer code. However, this takes into consideration all possible permutations $|X|!$, and would need the index (or "key") $k$ to be as large as $|X| \log_2 |X|$. I am happy with only $K << |X|!$ possible permutations (so long as $K$ is "big enough").


texts:
I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects itself using Bentley–Ottmann algorithm.

I planned to build non-self intersecting polygons by editing edges around intersection points, but problem is when you have two edges that intersect, you don't know which two of the four sides are inside, and which are outside of polygon.

I could use ray crossing algorithm to resolve this, but it is too slow. Its time complexity is O(n), and I'd have two do it at least two times for every intersection point. So it would be extremely slow with around 200k points of polygon.

So what I'm asking is, is there any faster way to divide self intersecting polygon into non-self intersecting ones.

I need this because I am doing polygon triangulation. I already done sweep-line triangulation algorithm for triangulating non-self intersecting polygons with holes. So I just need tho have array of these polygons as input.


texts: Merge-by-weight to solve reachability problems in trees and DAGs

texts:
Let $T = (V, E)$ be a tree with a designated root $r \in V$. The fact that the tree is rooted allows us to speak of "subtrees of $T$ rooted at some node $x \in V$". Let's say we have a (not necessarily injective) function $c: V \rightarrow \mathbb{N}$ that assigns a color to every node.

We want to find for every node $x \in V$ the number of distinct colors in the subtree rooted at $x$. So if $A(x)$ is the set of children of $x$, we want to find for every node $x$, the cardinality of the set

$S(x) = \bigcup_{y\in A(x)} S(y) \cup \{c(x)\}$

There is a rather simple algorithm that solves this problem offline in $O(n \log^2 n)$:

Process the nodes in depth-first order
Represent the sets $S(x)$ as a persistent, self-balancing binary search trees
For every node $x$, let $y \in A(x)$ be the child of $x$ that maximizes $|S(y)|$.  Now we just merge for every other child $z \in A(x) \setminus {y}$ the set $S(z)$ into the set $S(y)$ via insertion. We also insert $c(x)$ and now have $S(x)$ as a binary search tree and can give the answer for node $x$

We can even avoid the persistent trees by mutating the subresult for the heaviest child instead of creating a new set.

The typical argument I have seen to justify the bound is the following:

  A "move" consist of taking an element from a set and inserting it in another set.
  Let's prove that there's at most $O(n \log n)$ moves, each move can be done in $O(\log n)$, the total complexity is $O(n \log^2 n)$.

  When you are merging two sets you move all elements from smaller set (assume its size is $k$) to the bigger one, so every element in the smaller set now is in a set with at least size $2k$. In other words every element that has been moved $t$ times is in a set with at least size $2^t$, thus every element will be moved at most $O(\log n)$ and we have $n$ elements so in total there will be at most $O(n \log n)$ move operations.

(Quote from a Codeforces comment).

While this is a beautiful argument, it's not quite correct, because usually we remove duplicates, so sets don't in fact grow exponentially (for example if every node has the same color).

I am convinced that the bound holds, because I can prove it using structural induction. What I want to know is the following:

Is there a way to prove the $O(n \log^2 n)$ bound using an argument similar to the above, by bounding the number of "moves" of the color of a node? In other words, can the proof be "fixed" easily?
The argument from above would also hold in DAGs, not only in trees. However it seems unlikely that we could achieve a runtime better than $O(n \cdot m)$ to solve this problem in a DAG, so I guess there is no fix for the proof idea in this case. Am I right? Is there a good intuition for that?


texts: Hindley-Milner: How do I separate constraint generation and unification phases in Algorithm W when inferring types of patterns?

texts:
I am self-teaching myself Hindley-Milner type inference by writing my own implementation, separating tree traversal and constraint solving. The tutorials that I've been following only allow patterns that are variables, but I decided to implement pattern matching, and I've hit a wall concerning the separation of traversal and unification when inferring the pattern types.

My tree traversal phase maintains an "environment," a mapping of identifiers to polytypes. Patterns can introduce new bindings into the environment.

Given a let expression let id = expr in body, the tutorials that I follow compute id's polytype by generalizing expr's type with the current typing context, quantifying over all tvars not defined in the environment.

However, if non-identifier patterns are allowed, unification must be done in order to give identifiers in the pattern type schemes. For example, given

let (a, b) = foo in
body

, assigning a the tvar t0, b the tvar t1, and foo some monotype t3, t3 must be unified with (t0, t1) in order to give a and b the correct monotypes to generalize, at least to my understanding. Is it possible to me to separate constraint collection and unification when supporting patterns in my language, and if so, how? Thank you in advance!

For context, I am a high-school student not formally educated in computer science.


texts: Modal logic axiom S4, transitive and reflexive frame, tableaux solver

texts:
I have a difficult problem to solve which as mentioned in the title is related to modal logic axiom S4.
So, here is some background knowledge that can be useful:

S4 axiom is a class of transitive and reflexive frames
S4 satisfiability problem is PSpace-Complete
lastly solver for S4 does not terminate without a trick which will allow it to return a finite model.

Knowing all this, I have implemented a solver for propositional modal logic S4 and it also terminates with a finite model. In general solver uses Tableaux approach and generates graph in which the input formula is true. So, to outline what the algorithm does we have the following:

algorithm start by creating a graph with a single node with the input formula.
then we solve alpha, beta, gamma and delta formulas until each sub-formula is marked as being visited.
for termination part of the algorithm, every time a new node is about to be created (which is caused by delta formulas) we check whether the same node already exists in the graph. If yes, then we do not create a new node but we add an edge to the node that has that value.

This is enough to see what the algorithm does. What I am trying to do next is to prove that the algorithm is correct and will always work. For this purpose I will need to structure a formal proof.

So is anyone familiar enough with the topic to suggest what technique can be used to with the proof? What should be used bisimulation or filtration? Furthermore, it would be great if you could sketch out the proof if possible.

Any help would be very very appreciated.


texts: Recurrence formula for optimal binary search tree

texts:
This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For each key $k_{i}$, where $1\leq i \leq n$, we have a probability $p_{i}$ that a search will be for $k_{i}$.
We let the sequence $d =\{ d_{0},d_{1},\dots,d_{n} \}$, where $d_{0}<d_{1} <\dots<d_{n} $, be for values not in $k$.
For each key $d_{i}$, where $0\leq i \leq n$, we have a probability $q_{i}$ that a search will be for $d_{i}$.
The goal is to construct an optimal binary search tree.
Let us define $e[i,j]$ as the expected cost of searching an optimal binary search tree containing the keys $k_{i},\dots,k_{j}$.
Let $w(i,j) = \sum_{l=i}^{j} p_{l} + \sum_{l=i-1}^{j} q_{l}$.
The book gives the following equation as the recurrence formula for forming the optimal binary search tree:
$$
e[i,j] = \begin{cases}
q_{i-1} & \text{if } j = i-1, \\
\displaystyle\min_{i\le r\le j} \{e[i,r-1]+r[r+1],j]+w(i,j)\} & \text{if } i \leq j.
\end{cases}
$$
This formula makes sense for $i\leq j$, but I don't understand the case $j = i-1$.

Why is $e[i,i-1] = q_{i-1}$?


texts:
Assume that you are writing sorting algorithms, and that you want the ability to select between ascending and descending order. The only change required to do this for comparison sorts is to use the inverse of the comparison operator (for example: > becomes <). This begs the question, why is it not possible to change operators on the fly?

A simple bubble sort for ascending order:

private T[] BubbleAscending(T[] sortMe)
    {

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) > 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

Now we have to have a Bubble sort for descending order:

private T[] BubbleDescending(T[] sortMe)
    {

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) < 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

Now we have to have some logic to allow the user to easily select between them:

public T[] BubbleSort(T[] sortMe, bool descending)
    {
        if (!descending)
            return BubbleAscending(CopyArray(sortMe));

        else
            return BubbleDescending(CopyArray(sortMe));
    }

Wouldn't it be much simpler if we could do this?

public T[] BubbleSort(T[] sortMe, bool descending)
    {
        if (!descending)
            operator comparison = >;

        else if (descending)
            operator comparison = <;

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) comparison 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }


texts: Reconstructing a data table from cross-tabulation frequencies

texts:
Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two values occurs.

From the cross-tabulations, we can derive a set of possible rows $R$ of $D$ and maximum frequencies for each possible row.

How can we reconstruct the original table $D$? If there is not enough information to do so, how can we construct a possible table $D'$ that has the same cross-tab frequencies? In this case, is it possible to count the number of possible tables?

(Edit: As Vor noted, define a table as an unordered collection of rows. A permutation of the rows of a table yields the same table.)

For example, if $D$ has rows:

X  A  j
Y  A  k
X  B  j
X  B  j

We have three sets of cross-tab frequencies:

X  A  1
X  B  2
Y  A  1
Y  B  0

X  j  3
X  k  0
Y  j  0
Y  k  1

A  j  1
A  k  1
B  j  2
B  k  2

I would like an algorithm which will take the cross-tab frequencies as input and output the original table or a possible original table.


texts: Reference request: Monads, continuations, and other functional CS concepts

texts:
I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about.

I could visit Wikipedia and read about these two topics, but I'm looking for a reference which also help me learn about related matters that I don't even know exist. Is there a book on this particular topic (if it even qualifies as one)? Would I pick these things up by learning about type systems or language design in general? Should I just learn Haskell to get exposure?


texts:
The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\binom{n-k-\sum\limits_{i=0}^kx_i}k$$ in $O(nk·\log n)$ time, where $⊕$ is exclusive or.

Let $\sum_{i=0}^{k}x_i=S$.
The straightforward method is enumerating $S$ from $0$ to $n-2k$, and using dynamic programming to count nonnegative solutions to $\begin{cases}&x_0 ⊕x_1⊕\cdots⊕x_k=0 \\&\sum_{i=0}^{k}x_i=S \end{cases}$ (this is the number of winning positions for the first player of a Nim with $k$ piles and a total of $S$ stones, allowing empty piles). But it runs in $O(n^3 k)$ which is too large.

I think there may be some other dynamic programming technique to solve it, but cannot work out that. Any thoughts are welcome.


texts: Using pumping lemma to prove a language is not context free

texts: When using the pumping lemma for a context free language, if I write any $w \in L$ as $uvxyz$, is my goal to show that a string will not pump for ANY arrangement of $uvxyz$ that I choose, or is my goal to show that THERE EXISTS some arrangement of $uvxyz$ over $w$ that will pump?


texts: Classifying a problem involving matching bit arrays

texts:
First explaining the "reverse" use as a background:

There is an array A which contains N boolean values
There is an array B which contains N boolean values
I start iterating over array A and for every iteration I increment its current position by 1.
When corresponding bits at currentLocationA and currentLocationB in both arrays are true then the output become true.
Only when the current value in arrayA is true do I increment current position of arrayB.

The code for the "easy" direction is as following:

    var output = [];
    var outputLength = 10;
    var array1 = [false, false, true, true];
    var array2 = [false, true, true];

    var idx1 = -1,
        idx2 = 0;

    for (var i = 0; i < outputLength; i++) {
        idx1 = (idx1 + 1) % array1.length;
        output.push(array1[idx1] && array2[idx2]);
        if (array1[idx1] == true) { idx2 = (idx2 + 1) % array2.length };
    }

    return output;

Will output:
Result: false, false, false, true, false, false, true, false, false, false

This is the simple direction.

The problem I am looking to classify (and resolve):

How do I classify the opposite use case:
Given the output/result array - how can I get the input values required in array A and B? Input will be filled result array and a given size SizeA and SizeB for arrayA and arrayB.

Note: If the output array is longer than the input then the inputs wrap around


texts: In which situation do we choose randomized binary search instead of the normal binary search?

texts: Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same time complexity like that of the original binary search ?


texts:
I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax.

//Queue Q; source s; vertices u, v; distance to v d(v)
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q !empty) {
  u ← Dequeue(Q)
  for each neighbor v of u {
    Relax(u, v)
    if d(v) was updated by Relax and v not in Q
      Enqueue(v)
  }
}

But, can anyone explain why this improved version correctly finds the shortest path from $s$ to every other vertex in a directed graph with no negative cycles?

Also, what is the worst-case runtime if every shortest path uses at most $v$ edges?


texts:
You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+1][j], A[i][j-1] and A[i][j+1]. For corner elements, missing neighbors are considered of negative infinite value.

If someone has any understanding please share on how it decides which side to pick as that reduces complexity to $O(n \log n)$.

Solution is to consider the middle column, find its 1d maximum, then if it's not the peak, look at left and right side and pick a side which is larger. My doubt is, why is this algorithm correct?

Related material:

A) geeks link:
https://www.geeksforgeeks.org/find-peak-element-2d-array/

B) mit
This was shared in mit slides where it talks about 1d peak and then 2d peak
1)  https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

2) its second link gives an working example but not the reasoning
http://courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf
shows a working

C) Stackoverflow
There is also a StackOverflow discussion
https://stackoverflow.com/questions/23120300/2d-peak-finding-algorithm-in-on-worst-case-time

My doubt is How Can it predict based on seeing left and right element accurately that it has to go to the bigger half. I tried it a lot of times and it always works. So  I know it to be true. I then tried to create a counter example but I couldn't .

It's a very old question :
I initiated a chat but it didnt helped so asking question here : https://chat.stackoverflow.com/rooms/192196/2d-peak


texts: When generating a PDA from a CFG do I have a receiving state?

texts: Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.


texts: Compute several histograms with multiple filter conditions

texts:
I have a numerical dataset of $N$ columns ($\approx 150$) and $K$ rows ($\approx 60000$).
On a user interface, you can apply a filter to one or more columns. We can call the number of filters = $Z$ (with $Z \le N$). Those filters are double sliders allowing to get a min/max for the column. For each filter, I would like to compute the histogram by applying all filters except this one.
The simplest method would be for each filter, to apply all other filters in the complete dataset and compute the histogram of this remaining column. That leads to a $O(Z^2)$ filtering on the dataset and poor performance with an important number of $Z$ and also $K$.
Is there a smarter way ? I have a "feeling" there is probably a way in $O(Z)$ but I am not able yet to clear it in my mind to write it :). It looks quite similar to the problem of the product of an array except self in term of thinking.
Maybe a more concrete example may help
On a e-commerce, you are selling RAMs and you have a filter by:

price
number of modules
frequency
memory size

If you filter the price between 100€-200€ and a frequency above 3000Mhz, you will mainly have a memory size of 16Gb.
The benefit of the histogram is to see on the "price" slider, in which direction you may have more result with the smallest change. For example going below 100€ will not provide a lot more result as there is nearly no ram below 90€. However, if you increase to 250€ you may have a lot more choice for this range of frequency. Similarly, if you reduce the frequency, you will end up with more choice (lower frequency is cheaper so maybe 32gb will be available at 200€.
To see that:

you need to compute the distribution of the price after applying the filter on frequency only
then compute the distribution of the frequency after applying the filter on price to have the number of product available below 3000Mhz.

The objective is to be able to render something like :

The histogram is available on the complete range of even if there is a filter on this given range (blue section). This is quite simple if there is only 1 filter as you compute only once the histogram but on my case, depending on other filters, this histogram varies.
I hope this example makes it clear.


texts: Can we make a problem harder than NP and coNP if they are not equal?

texts:
Let us assume that $\mathsf{NP} \neq \mathsf{coNP}$. Consider the graph 3-colorability problem.

Since $\mathsf{NP} \neq \mathsf{coNP}$ implies $\mathsf{P} \neq \mathsf{NP}$ and 3-coloribility is $\mathsf{NP}$-complete and its complement is $\mathsf{coNP}$-complete , we have:

3-coloribility is not in $\mathsf{P}$, i.e. there are no polynomial-time algorithm for deciding if a given graph is 3-colorable.
non-3-coloribility is not in $\mathsf{NP}$, i.e. there are no polynomial-time verifier with polynomial-size certificatesfor non-3-colorability.

However, we know that for many classes of graphs, polynomial algorithms exists for 3-colorability and also they have polynomial-time verifiers with polynomial-size certificates for non-3-colorability. But this is not the case for all graphs since we we assumed that  $\mathsf{NP} \neq \mathsf{coNP}$.

We can define the following problem:

  Input: a graph $G$,
  Task: determine if $G$ is 3-colorable or non-3-colorable and provide a certificate for the answer. The certificate is either a 3-coloring or a non-3-colorability certificate.

What is the complexity of this problem?

YES version is in $\mathsf{NP}$ . And the NO version is in $\mathsf{coNP}$. Note that the answer is not always YES since $\mathsf{NP} \neq \mathsf{coNP}$.


texts: show that NP is a subset of decidable languages

texts:
More specifically the problem says: "Let us call the set of decidable languages D. Show that NP ⊆ D"
My problem is that I always assumed that NP is decidable, but to prove it, I never thought it
Somebody have any idea about how do it? or start resolving it?
I think I can prove it saying something like the NP problems effectively end in a polynomial time (although not deterministic) so there must be a MT-ND that accepts it and always ends, I suposse


texts:
I'm currently developing my degree thesis, and the lab's idea is to design a new micro architecture, and then, be able to compile stuff for this architecture. So the question is, how do you instruct a compiler to generate your new assembler???
The general idea is to be able to compile with gcc and run netbsd or similar kernel with this new architecture.
Well, thanks a lot!


texts: Is the intersection of $k \geq 3$ graphic matroids in P?

texts:
It is known that intersection of three general matroids is NP-hard (wiki), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.

A special case of a problem I am working on can be solved by intersection multiple graphic matroids, but I haven't been able to find, whether this problem is in P. Is it known? Can someone refer me to a paper or something?


texts: Is the Berman-Hartmanis Conjecture Solved?

texts:
The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on One-Way Functions and Polynomial-Time Isomorphism).

Since the Cook-Levin theorem states that $NP$ is polynomial-time reducible to $NP$-complete.

Does the Berman-Hartmanis conjecture state anything about the converse statement? I.e. if $NP$ is polynomial-time isomorphic to $NP$, then one-way functions do not exist?

It seems to me that proving the converse and proving the non-existence of one-way functions proves the $P=NP$ problem.

Furthemore, is the Berman-Hartmanis conjecture solved?


texts: Null Characters and Splitting the String in the Pumping Lemma

texts:
So I'm really struggling with the pumping lemma.  I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question.  Here is an example, take the problem prove that $L = \{w | w$ contains more $0$'s than $1$'s over the language $\{0,1\} \}$ is not regular via the pumping lemma.

So I choose the string $01^{p}0^{p}$.  Since this is a regular language pumping lemma problem I know that:

for each $i > 0, xy^{i}z \in A$,
$|y^{i}| > 0$, and
$|xy| < p$

I am little uncertain about other possibilites though, such as if $x$, or $z$ can be null (obviously $y$ can't by condition 2).  I assume that this isn't possible since I don't think the preceding or trailing whitespace is considered part of the string, but I'm not sure.  Is it possible for $x$ or $z$ to be null?


texts: In the Subset Sum problem can some of the given numbers $a_1,a_2,a_3,\dots,a_n$ be the same? For example, we might have $[1,1,1,2,3,4]$ and the target is $5$? Can I assume that I have a specific solution with numbers $2$ and $3$ and $1,1,1$ and $2$ is not?


texts: How does the length of the output of a problem inform its complexity?

texts:
Consider the decision problem: Subset sum. For an input set of integers, it asks for a Yes/No answer to the question of whether or not we can find a subset of elements of this input that add up to 0. The output for this problem is $O(1)$ and simple (e.g. 1/0). This problem is NP-Complete, which as far as I understand is only defined for decision problems.

Now consider a problem associated with Subset sum that asks to output all such subsets that add up to 0.  As far as I understand, this is an optimization problem.

Moreover, the output of this problem could grow as $O(2^N)$ if $N$ is the size of the input array (i.e. the output grows as fast as the cardinality of the power set of the input).  If so, what does this say about the complexity or complexity class of this optimization problem?

More generally speaking, does the size of the output of an optimization problem provide a necessary lower bound on the complexity of the optimization or associated decision problems?


texts:
I think I barely understand the usefulness of asymptotic notations. And I came across small o and I want to prove that statement is true. But I have no idea how to start.

Those are 2 extra problems with the same idea :
Prove that 1000.n^2+ 1000.n ≠ o(n^2) And Prove that 5.n + 10 ≠ o(n)

Note: someone marked this question as repeated by D.W., I looked D.W. all his questions and I didn't find any similarity.


texts: Difference between capacity miss and conflict miss

texts:
Premise:

Two types of cache miss:  capacity miss, conflict miss\
Cache contains only 2 sets, SET 1 and SET 2

Problem:

If data A maps to SET 1 and it doesn't exist in SET 1 while SET 1 is fully occupied and SET 2 is not fully occupied, I know this case is called conflict miss. But what should it be called if the same case but entire cache is fully occupied? Is it capacity miss or conflict miss? Once the cache is fully occupied, conflict miss will never happen?


texts: Can a public key be used to decrypt a message encrypted by the corresponding private key?

texts:
From what I have seen about usage of a pair of public and private keys, the public key is used for encrypting a message, and the private key is used for decrypting the encrypted message.

If a message is encrypted by the private key, can it be decrypted by the corresponding public key?

If yes, can you give some examples of when this case is used?

Thanks.


texts: How to prove transitivity in small-o of asymptotic analysis?

texts:
Here is my proof, but I am not sure whether it is correct.

We know:

$\qquad \begin{array}{l}
 \forall {c_1},\exists {n_1},0 \le f\left( n \right) \le {c_1}g\left( n \right),\forall n \ge {n_1} \\
 \forall {c_1},\exists {n_2},0 \le g\left( n \right) \le {c_1}h\left( n \right),\forall n \ge {n_2} \\
 \end{array}$

Hope to prove:

$\qquad \begin{array}{l}
 \forall c,\exists {n_0},0 \le f\left( n \right) \le ch\left( n \right),\forall n \ge {n_0} \\
  \Rightarrow 0 \le f\left( n \right) \le {c_1}g\left( n \right) \le {c_1}\left( {{c_1}h\left( n \right)} \right),\forall n \ge \max \left\{ {{n_1},{n_2}} \right\} \\
 \end{array}$

Let $c = {c_1}^2$. Then,

$\qquad 0 \le f\left( n \right) \le {c^2}h\left( n \right),\forall n \ge {n_0} = \max \left\{ {{n_1},{n_2}} \right\}$

Is there any mistake?


texts: Why is the Marking Algorithm takes O(number of marks) ?

texts:
I am referring to the Marking algorithm defined in this article: https://arxiv.org/pdf/1602.00621.pdf

The Marking method is defined at the bottom of page 4 and has a pseudo code at the beginning of page 5.

In page 7 they claim "The runtime of the marking stage is O(B)". B being an upper bound for the number of marks of the marking algorithm.

To me It seems like the Marking algorithm should take O(|A|n), A being the positions in its input.

Can someone help me understand this?


texts: Book recommendations on the analysis of randomized algorithms

texts:
I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to construct the proof of correctness for such algorithms.
I am currently reading Probability and Computing - M. Mitzenmacher, E. Upfal, which I find to be a good introduction to this topic.
What are your suggestions?


texts: Lower bounding the minimum equivalent graph

texts:
The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$.

The minimum equivalent graph $G' = (V,E')$ is the smallest graph with the same reachability as $G$ with the property $E' \subseteq E$.

Consider the case when $G$ is strongly connected.

The transitive reduction is formed by an arbitrary Hamiltonian cycle, so $|E^t| \equiv |V|$ and so we must have $|E'| \geq |V|$.  We want to find a polynomial time algorithm which finds a tighter lower bound than $|V|$ for $|E'|$. I'm wondering if this is possible at all, assuming $P \neq NP$.

If $|E'|>|V|$, then $G$ can not contain a Hamiltonian cycle . So if we can find a tighter bound in polynomial time, then we have determined the existence of a Hamiltonian cycle in polynomial time.

I think this means that efficiently lower bounding this problem is a wild goose chase. The best bound we can consistently hope for is $|V|$.

Is this a too pessimistic interpretation?


texts: When can you "invert" an equation in the lambda calculus

texts:
Suppose that $M$ is a full model of the simply typed lambda calculus. Suppose each base type is infinite.

Now suppose that $f$ and $g$ are two functions in $M$ (not necessarily in the same domain) that are not definable by any pure term, and that $\alpha$ is a pure term of the $\lambda$-calculus such that:
$$M(\alpha) g = f $$

My question is: when is it possible to find a pure term $\beta$ such that
$$g=M(\beta)f$$

Are there easy to state necessary or sufficient conditions? I have been unable to find counterexamples when gs type complexity is higher than fs,  so maybe that is a sufficient condition?

A couple of examples:

if $f$ is the converse of $g$:
$$f=M(\lambda xyz. xzy)g$$
then we can find such a $\beta$ -- in this case, letting it also be $\lambda xyz. xzy$.

Similarly If $f$ is application to $a$:
$$f = M(\lambda xy.yx)a$$
then $a$ is $f$ applied to $\lambda x.x$: $$a = M(\lambda y.y(\lambda x.x))f$$

Lastly, if $x$ is a variable in some base type and $f=M(\lambda xy.x)a$, then I don't think there is any pure term such that $a=M(\beta)f$.


texts: Given snapshot and boolean circuit how to compute coNP formula?

texts:
Theorem 6.20: If $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$ then $\mathsf{EXP\text{}} = \Sigma_2 ^{p}$.

My attempt  : Let $L \in \mathsf{EXP\text{}}$. Then $L$ is computable by an $2^{p(n)}$-time Turing machine $M$, where $p$ is some polynomial. Let $x \in \{0,1\}^n $ be some input string. For every $i \in [2^{p(n)}] $, we denote by $z_i$ the encoding of the $i$th snapshot (the machine's state and symbols read by all heads) of $M'$s execution on input $x$. If $M$ has $k$ tapes, then $x\in L \iff $ for every $k+1$ indices $i,i_1,i_2,\cdots,i_k$, the snapshots $z_i,z_{i_{1}},\cdots,z_{i_{k}}$ satisfy some checkable criteria.

As $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$, then there is a $q(n)$-sized circuit $C$ (for some polynomial $q$) that computes $z_i$ from $i$. Now the main point is that the correctness of the transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate (namely, one that checks that the transcript satisfies all local criteria).
Hence, $x\in L$ iff the following condition is true

$$ \exists C \in \{0,1\}^{q(n)}  \forall i,i_1,i_2,\cdots,i_k \in \{0,1\}^{p(n)} T(x,C(i),C(i_1),\cdots,C(i_k)) = 1$$

  Question : I am not able to understand, how transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate ?

Reference : http://theory.cs.princeton.edu/complexity/circuitschap.pdf


texts:
What would be the practical consequences of ZPP=exptime.
It would be pretty ridiculous if the was true but what if it was?


texts: Converse of Impagliazzo, Kabanets, Wigderson

texts: I am trying to prove that $\text{NEXP} = \text{MA} \Rightarrow \text{NEXP} \subseteq P/\text{Poly}$. I tried to approach the result via trying out the contrapositive, that $\text{NEXP} \nsubseteq P/\text{Poly} \Rightarrow \text{NEXP} \ne \text{MA}$ but I couldn't get anywhere. Can anyone give me a hint to proceed?