texts:
Disparity essentially means the distance of a corresponding pixel in another image ( in pixels). This is clear and understood. When I looked after how the depth is related to disparity, then I found the formula

Base * Focal / disparity = Depth

This equation looks interesting, For example,  Base is 50 mm, and Focal is 2 mm  then

    (50*2)/2 = 50 ( for dispary 2)
    (50/2)/3 =  33.3 ( for disparity 3)

My question now is, just one-pixel change ( from 2nd pixel to 3rd pixel), the difference in the depth is (50 - 33.3).  I am aware there is something subpixel concept, but even then how this subpixel is still going to fulfill the gap ( 50 - 33.3 ) by means of "one single" pixel?

Any help is really appreciated.


texts: What is The correct terminology for expressing *this* notion of complexity

texts:
Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$. For the purposes of this question, $Al_j$ and $Al_i$ are the same.

Or, if I have two systems that produce the same output given the same input, then we can treat these systems as the same.

Generally, if two objects do the same things (produce the same output for identical input, convey the same information as output), then these objects are identical. The processing of the systems are not relevant. We're only concerned with the output of the systems, objects, entities, etc.

Now, there are many such identical systems. Say $T_i$ is some set of all identical objects/entities/systems that do some same thing. Let $t_i^*$ be the object in $T_i$ with the smallest Kolmogorov complexity.

  Is there a conventional terminology for expressing $t_i^*$?

An example of a $T_i$ may be the set of all proofs for a particular theorem. (Here the Kolmogorov complexity of all theorems includes each intermediate theorem invoked in its proof (so basically each theorem would first be expressed in axioms first and computing the complexity of that expression)). I may be interested in referring to the least complex theorem (using the aforementioned notion of the complexity of the axiomatic expression of the theorem).

Things can be defined by form or by function. I understand that Kolmogorov complexity traditionally considers the former, while I am concerned with the Kolmogorov complexity of the latter. A picture has a defined form, and an algorithm that only produces that picture is no different from the picture itself. What about an algorithm that produces different output. We could look at the form of the algorithm, or look at its function. Looking at function, all correct algorithms for a particular problem are identical. Bogosort is identical to quicksort which is identical to mergesort, heapsort, etc.
I am concerned with the smallest Kolmogorov complexity of any sorting algorithm.


texts:
Is $DSPACE(f) \subseteq DTIME(f)$ always?

For example, if we have a language $A\in DSPACE(log^2(n))$ can we say that $A\in P$ (and  subsequently in NP and coNP) since $DSPACE(log^2(n))\subseteq DSPACE(n^3) \subseteq DTIME(n^3)$?

I know about $ DTIME(f) \subseteq DSPACE(f) \subseteq DTIME(2^{O(f)})$ but $DTIME(2^{O(f)})$ is too big in this case.


texts: What happens when sink transition is enabled

texts:
Well I guess it is only a matter of definition but I've failed to find certain answer to the following question:

In a Petri net if transition has k inputs and zero outputs what is considered to happen when transition fires? Do we have just k - 1 token left and then just transition is not enabled?


texts: Data structures for general (non-tetrahedral) cell complexes

texts:
For 2D polygonal meshes, the QuadEdge and HalfEdge data structure representations are sufficient to store and enable efficient query of all topological and incidence information. Are there compact and efficient data structures for 3D polyhedral meshes? I know there has been some recent work on compact representations for tetrahedral meshes, like, for example SOT. I don't know enough about these to know if they generalize to unstructured non-tetrahedral meshes.

I can imagine that half-edges might generalize to half-faces with associated half-edges, but it seems like that is a lot of data to store, and there might be more compact representations. I should add that I really only care about retrieving facet information (like which facets are on the boundary, which facets belong to a certain cell); the edge incidence information is not as useful.


texts: Efficient cardinality of set overlap relation

texts:
Assume that we have a set S of sets s.
Every pair (s,s') in SxS can be overlapping or not.
How can we efficiently compute the number of pairs (s,s') that are overlapping, i.e. that share at least one element?
Additional: actually each set s occurs a number of times (S is a multiset). I have tried to create a matrix M of scipy.sparse.csr_matrix that stores the subset partial order over S. Then I have tried to add the additional edges for overlaps through M.T.dot(M) to then later compute f.dot(M).dot(f.T), where f gives the frequency for each s. Unfortunately M.T.dot(M) becomes too large, so if anything, we probably have to propagate the counts through the subset partial order one after the other.
Hints: it might seem apparent at first to just take the sum over the union of all elements in all s of their frequency squared to sum up the number of pairs sharing one particular element. However the problem is that this counts many pairs multiple times. For example {a,b} is counted for a and also for b. This is why it seems important to use the subset partial order.
Any ideas?


texts:
I am working with a time series which is, in fact a pressure signal.
There are special "events" in the signal that I am looking for.for example where the signal suddenly goes up or down or where there is an abrupt peak in the signal.I have shown some of them with red arrows in the picture.
I am familiar (but not an expert) in the field of data science and machine leaning. What is the best way to use AI techniques to automatically detect and classify these events?
Thanks in advance!


texts: What is the difference between control flow graph & interprocedural control flow graph?

texts: I am doing research on control flow analysis on aspect oriented programs and I found in some papers an interprocedural approach for doing control flow analysis on others call graph or control flow graph. Is there a real difference between control flow graphs and interprocedural control flow graphs?


texts: NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

texts:
Consider the following decision problems:

$CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components}

$E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected components}

I'd like to show this two problem are in $NL$. I Know it's possible to guess a vertex from each connected component and then verify the connectivity of the component (by guessing paths to other vertices). But how can I verify all guessed vertices are different, when it's impossible to hold $k$ vertices on the work tape?


texts: P reduction between np-complete to np-complete

texts:
given 2 lagnauges A,B which are npc.
is there a reduction function from A to B $A \leq_PB$ ?

my idea was to say that since they are decideable,
we can do this:
$$
f(x) = \begin{cases} y \in B & \text{ } if x \in A \\y \notin B & \text{if }x \notin A.\end{cases}
$$

is this is correct? or its not something that can be true? / depands on p equal or not equal to np


texts: Incremental strongly connected components

texts:
For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data structures achieve the best known amortized complexity for these operations?

If the graph was undirected, the answer would be the union-find structure. And as undirected graphs can be seen as special cases of directed graphs, the (ever so slightly) superconstant lower bound carries over.

For a linear upper bound, the strongly connected components can be computed from scratch after each edge addition, without recycling any data at all. I wonder if there is any way to do better.

In the setting where I need this, I somehow expect non-trivial SCCs to be the exception rather than the rule. And in the absense of cycles I can achieve linear time in total (that is amortized constant time per operation). [EDIT:] Let me clarify what I mean. Of course, in the absense of cycles I do not need to keep track of SCCs at all. The amortized constant time is for what I do in my setting besides worrying abouts SCCs.

So I would also be interested in data structures that are, in general, not better than the above upper bound but use amortized constant time per operation as long as the graph remains a DAG.


texts: What is the difference between available expressions analysis and very busy expressions analysis?

texts: I am having trouble understanding the conceptual meaning of the two kinds of analysis. I know the equations and how to solve the problems and I know how one is a forward data-flow analysis while the other is a backwards data-flow analysis, but there is still something missing in the explanations I have seen so far, in a higher level.


texts: If A is polynomial time reducible to B and B is in NP, then A is in NP

texts:
If $A\leq_p B$ and $B$ is in $NP$, is it true that $A$ is in $NP$?

What about : "if $A\leq_p B$ and $B$ is in $coNP$, then $A$ is in $coNP$"?

Thanks in advance.

I think both hold. If $B$ is in $NP$, then the yes-instances of $B$ can be verified in polynomial time. If $A \leq_p B$, I can "translate" an instance of $A$ to a instance of $B$. Then I can use the verification algorithm for $B$ to check the yes-instances of $A$. The same should be valid for the second affirmation. I'm not sure though.


texts: What time complexity is a reachability algorithm?

texts:
I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive reachability matrix in RAM. What sort of time complexity would be possible for an algorithm to calculate all reachable nodes in a directed graph, from a single node?

Here's a naive algorithm I came up with, I'm not sure of the time complexity of this. $O(V!)$?

It seems to have an $O(V)$ spacial complexity though.

I've read about the Bellman-Ford algorithm with a time complexity of $O(EV)$ which is essentially $O(V^3)$ and the Floyd-Warshall algorithm which is $O(V^3)$. They require $O(V)$ and $O(V^2)$ space complexity, respectively.

The problem is only inputs can be determined in constant time. So, one would have to find (in $O(V)$ time)  all outputs for a particular node. What I actually did in my solution is invert the graph using a similar technique, before running DFS. But I don't know if this is optimal... Also, due to a copy of the graph being stored in memory, my solution has a spacial complexity worse than the bellman-ford algorithm. If this time complexity is also worse, I may as well use bellman fords algorithm


texts: Hamming code extension with additional parity bit

texts:
Let $Ham$ be the $[7,4,3]_2$ Hamming code.

It is known that $\{w(c):c\in Ham\}\subseteq\{0,3,4,7\}$, where $w(c)$ is the Hamming weight of the word $c$.

A code $C$ of length $n$ is called cyclic if $\forall c=(c_0,\dots,c_{n-1})\in C:(c_{n-1},c_0,\dots,c_{n-2})\in C$.

A straight forward extension for $Ham$ to an $[8,4,4]_2$ code $C$ is a code which is restricted to the $7$ first coordinates is $Ham$ and the last (new) coordinate is a parity bit for the first (original) $7$ ones.

This is true since $C$ is of length $8$ which is $7$ for the first $Ham$ coordinates and another $1$ for the parity bit. Also we end up with the same number of codewords, so the dimension is still $4$. But, now $\{w(c):c\in C\}\subseteq\{0,4,8\}$.

The question is whether $C$ is a cyclic code? and a more general one is what are all the $[8,4]_2$ cyclic codes (I mean is there a certain criterion)?

I know that $Ham$ is cyclic.

I can also say that in $Ham$ we can look at the zero codeword, the all $1$'s codeword and two other codewords $x,y$ with all their cyclic movements this gives us $1+1+7+7=16$ codewords.


texts: How do I solve a maze using velocity and acceleration?

texts:
I need to solve a maze. I can move an object around in a 2D maze by giving it 1 acceleration in any 8 of its 8 directions.
The object starts at rest at 0 velocity.
By only adding an acceleration at each step, I need it to be able to solve the maze and finish at the end position with a final velocity of 0.
This maze is shaped with big open areas and not narrow corridors of tight corners.
It should also take the least amount of steps possible to get to its destination.

This as you can imagine, would look different than simply finding the shortest path.


texts: Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

texts: I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only interested in the design, no coding. I believe I can use the approach of kd-trees assuming that the query line is also axis aligned, say x-axis. Any help will be pretty much appreciated. Thanks in advance


texts: How does the number of clauses affect the difficulty of a 3-SAT problem?

texts: What is the relationship between the number of clauses and the difficulty of a 3-SAT problem?


texts: What are the strongest known type systems for which inference is decidable?

texts:
It's well known that Hindley–Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without any annotations.
Adding Haskell-style typeclasses seem to preserve this decidability, but further additions makes inference without annotations undecidable (type families, GADTs, dependent-types, Rank-N types, System $\omega$, etc.)
I'm wondering: what is the strongest known type system with completely decidable inference? It's going to lie somewhere between Hindley–Milner (completely decidable) and dependent-types (completely undecidable). Are there aspects of DTs which can be added which preserve inference decidability? What research has been done to see how far this can be pushed?
I realize that there is not a single strongest system: that there are likely infinite small, incremental changes that can be added to HM keeping inference. But there are likely a few practical candidates of systems that have been discovered.
Edit: given that there is no "strongest" system, I will accept an answer that outlines the notable systems that extend Hindley–Milner with decidable inference. Examples could be Liquid Types, Rank-2, etc.


texts: Reference Request: Overlaps between complexity theory and dynamical systems?

texts:
Per Wikipedia:

  In mathematics, a dynamical system is a system in which a function
  describes the time dependence of a point in a geometrical space.
  Examples include the mathematical models that describe the swinging of
  a clock pendulum, the flow of water in a pipe, and the number of fish
  each springtime in a lake.

  At any given time a dynamical system has a state given by a set of
  real numbers (a vector) that can be represented by a point in an
  appropriate state space (a geometrical manifold). The evolution rule
  of the dynamical system is a function that describes what future
  states follow from the current state. Often the function is
  deterministic; in other words, for a given time interval only one
  future state follows from the current state however, some
  systems are stochastic, in that random events also affect the
  evolution of the state variables.

Is there any result on dynamical system (i.e. solving dynamical equations, finding asymptotic states to a system, dynamics in chaotic system) with complexity theory, hardness for finding a solution, etc.?

Thanks


texts: Determining initial and final states from FA diagram

texts:
I am new to automata. And learning to find concatenation of two FAs. But this one has confused me

I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final state or does it mean both initial and final state because it is on the start?? Just clear me on this that what is initial state and what is final state in FA 1? Then I'll take it from here and will be able to do concatenation.

P.S I know that +- in a state mean both initial and final state but I don't know about double circle form. Kindly help me on this.


texts: Is it possible that Co-NP = P but NP != P

texts:
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (let's say time and memory problems, the algorithm gets lost in the reasoning).

Then Co-NP = P because we can verify unsatisfiable instances in polynomial time. The certificate of unsatisfiability is the formula itself.

But then is it still possible that P != NP?


texts: Should I describe automata before describing grammar?

texts: Let's say I want to describe some new grammar formalism, which doesn't coincide with known grammar sets. Should I always previously describe corresponding equivalent automata and why?


texts:
Suppose I have two processes of 50 bytes and have only one partition (hole) of 100 bytes. Suppose the first process takes up the partition and 50 bytes is remaining . Can the second process reside in the same partition even if free space is available or will internal fragmentation occur in case of first fit?

Also is it true that if internal fragmentation is present then external fragmentation is also present?


texts: Running time of naive recursive implementation of unbounded knapsack problem

texts:
How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more detail.

For reference, here's a bit of Python code that implements the brute-force solution. Note that this can run for a long time even on smallish inputs. One of the interesting things about Knapsack is some inputs are lot harder than others.

import random, time
import sys

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

    def __repr__(self):
        return "Item(weight={}, value={})".format(self.weight, self.value)

def knapsack(capacity):
    if capacity==0: return ([], 0)
    max_value = 0
    max_contents = []
    for item in items:
        if item.weight <= capacity:
            (contents, value) = knapsack(capacity-item.weight)
            if value + item.value > max_value:
                max_value = value + item.value
                max_contents = [item]
                max_contents.extend(contents)
    return (max_contents, max_value)

def generate_items(n, max_weight, vwratio=1):
    items = []
    weights = random.sample(range(1,max_weight+1),n)
    for weight in weights:
        variation = weight/10
        value = max(1, int(vwratio*weight + random.gauss(-variation, variation)))
        item = Item(weight, value)
        items.append(item)
    return items

n=30
max_item_weight=100
capacity=100

items = generate_items(n=n, max_weight=max_item_weight, vwratio=1.1)

st = time.time()
solution, value = knapsack(capacity)
print("completed in %f"%(time.time() - st))

Note that this algorithm can be improved upon nicely by memoizing yielding a O(nW) pseudo-polynomial time solution, but I was interested in understanding how to analyze the brute-force algorithm more precisely.


texts: Characterisation of Turing completeness?

texts:
I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language.

For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of variables). That gives an easy way to say if a language is Turing complete, as soon as we've found out that it is imperative.

Hence my question is there any similar, characterization of Turing completeness which would work for any language?


texts: Efficient algorithm for constructing the Edge-Adjacency Matrix

texts:
I've been recently working with graph, more precisely edge-adjacency matrices. I found this source, which explains the concept intuitively.

Now, when I am trying to implement this conversion, I was wondering what is the most efficient way to transform a standard (node) adjacency matrix into an edge-adjacency matrix?

Thank you very much.


texts: Finding the two node-disjoint paths, minimizing the sum of their lengths

texts:
Given an undirected graph and a start and end node, I am trying to find two node-disjoint paths such that the sum of their lengths is minimized.  In particular, each path must start at the start node, end at the end node, and no node (other than the start or end node) can be visited by both nodes.  Is there an efficient algorithm to solve this problem?
I know that if I just need the shortest path, I can use Dijkstra's algorithm, but finding one path with Dijkstra's algorithm and then searching for another is sometimes not optimal at all, since nodes in the first path may have blocked a possible and way shorter path.
I have tried implementing the node_disjoint_path algorithm from the Python networkx package. But I must say that the result is very varying from okay to really bad.  My network is not that big. "Only" 6000 nodes and 7500 edges.


texts: I want to survey the state-of-the-art in image segmentation. Is there a paper on how to segment multiple objects in an image? The segmentation papers I read, normally identify one of the many objects in the image. This object is typically in the center of the frame, or most-foreground compared to other objects in the image. I'm looking for a way to identify all different objects in an image simultaneously. Is there any recent work on this?


texts: Do exponential functions grow faster than logarithmic?

texts:
For example:

$f(n) = n(log_2 n)^4$ vs $g(n) = n^{1/3}$

Does f(n) grow slower than g(n) as a general rule, even for decimal exponents? I tried doing a limit test but symbolab limit calculator is saying that Steps are currently not supported for this problem.

I graphed them over a large range and it does appear that g(n) grows asymptotically faster.


texts: On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

texts:
in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.

Besides, it's easy to see that the KP problem is a special case of the QKP.

How should one proceed to prove the NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem?

CCQKP:

$$max\ \sum_{i=1}^{n} \sum_{j=1}^{n} x_i x_j c_{ij}$$
$s.t$
$$\sum_{j=1}^{n} a_j x_j \leq C$$
$$\sum_{j=1}^{n}x_j = 1$$
$$0 \leq x_j \leq 1,\ j = 1,...,n$$
$$\sum_{j=1}^{n}z_j = k$$
$$z_j \in \{0,1\},\ j = 1,...,n$$

I'm aware that we usually talk about the hardness of Decision Problems even tough I'm formalizing the Optimization version of it.


texts: Iteratively find and modify a certain element in a set in $\log n$ per iteration

texts:
I've looked around and can't find my answer.

I have a set of $n$ numbers. In each iteration I would like to find an arbitrary number and change it. Is it possible to perform each iteration in $\log n$ time?

There are data structures like a min-max heap which allow insertion and deletion in $\log n$ time, but that only allows deletion on the min/max values.


texts: How can we find the number of pairs of intersecting ranges on a circular number line?

texts:
I recently thought of and managed to solve this algorithmic problem:
On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers A and B, such that all A and B are unique. Each pair of integers then represents the starting and ending points of a range on the number line. How many distinct pairs of ranges intersect?

^^ In this example, 4 distinct pairs of segments intersect.
Obviously, there is a O(N^2) brute-force solution: just test all possible pairs in O(1) time each. However, I also thought of a O(NlogN) sweep-line algorithm: treat every A as a "segment start event" and every B as a "segment end event". Then, keep a variable curr_in_range (originally 0) that stores the current number of segments that we currently see, and then iterate through the events in sorted order of their positions on the number line. Every time we add another segment, add curr_in_range to the answer (because this new segment will intersect with every other segment that we can see) and increment it as well. Every time we remove a segment, decrement curr_in_range. In the end, this gets us the correct answer.
Happy with this algorithm, I decided to tackle a slightly modified version of this problem: What if the number line is circular? As in, it has a specified length L such that the number line contains numbers in the range [0, L)? In this case, each range would still be specified by two distinct integers A and B, but let's just say the range is always counterclockwise starting from A and ending at B. Could we still find the number of pairs of sectors that intersect in less than O(N^2) time in this scenario?
Here's my thought process on this problem:
We should be able to use a very similar algorithm to the one described above. Completely copying it wouldn't work, though, because the sectors can have B < A when it crosses over 0. My idea was to initially have curr_in_range equal to the number of sectors that cross over 0 (instead of just it at 0 like we did in the above algorithm). Then, we could treat every sector as a "sector start event" and a "sector end event", and do the same process that we did.
However, after extensive analysis, I found why this approach doesn't work. This approach won't work because it overcounts some of the intersections, as sometimes two sectors can intersect in 2 places. This is where I'm stuck.

^^ Our sweep-line algorithm will count 2 distinct pairs that intersect, when there is actually only 1.
But besides this overcounting, I found that this current algorithm isn't doing a single other thing wrong. I coded a O(N^2) brute-force algorithm and tabulated all the distinct pairs that it found, and also tabulated the distinct pairs found for the current algorithm. For every randomly-generated test case, these two tables were the same. In other words, our current algorithm is correctly detecting every intersection there is to be detected, but it just happens to overcount some of them.
So, sorry for a really long post, but my final question is:
Can someone come up with an algorithm that solves this problem? Is my thought process close to a solution or completely off?


texts: The optimized numbers of variables and clauses to encode a graph coloring problem in CNF

texts:
Problem Statement

Given a finite graph $G = \langle V, E\rangle$, consisting of vertice set $V$ and edge set $E$, and a finite set of colors $C$, a problem instance of graph coloring is to assign each vertex $v \in V$ a $\text{color} (v) \in C$ such that $\forall \langle v, w\rangle \in E, \text{color}(v) \not= \text{color}(w)$. Now we encode an instance of graph coloring problem into a CNF (conjunctive normal formula) $F$.

  Note: The word "encode" means that we'll know a graph coloring problem if a CNF is given, and also will know a CNF if a graph coloring problem is given.

What is the minimal number of propositional variables in $F$?
What is the minimal number of clauses in $F$?

Original Version

A solution to a graph coloring problem is an assignment of colors to vertices such that no two adjacent vertices have the same color. Formally, a finite graph $G = \langle V, E\rangle$ consists of vertices $V = \{v_1, \cdots, v_n\}$ and edges $E = \{ \langle v_{i_1} , w_{i_1} \rangle , \cdots , \langle v_{i_k} , w_{i_k} \rangle \}$. The finite set of colors is given by $C = \{c_1, \cdots , c_m \}$. A problem instance is given by a graph and a set of colors: the problem is to assign each vertex $v \in V$ a $\text{color}(v) \in C$ such that for every edge $\langle v, w\rangle \in E$, $\text{color}(v) \not= \text{color}(w)$. Clearly, not all instances have solutions.

Show how to encode an instance of a graph coloring problem into a PL formula $F$. $F$ should be satisfiable iff a graph coloring exists.

Describe a set of constraints in PL asserting that every vertex is colored.
Since the sets of vertices, edges, and colors are all finite, use notation such
as “$\text{color}(v) = c$” to indicate that vertex $v$ has color $c$. Realize that such an assertion is encodeable as a single propositional variable $P^c_v$.
Describe a set of constraints in PL asserting that every vertex has at most
one color.
Describe a set of constraints in PL asserting that no two connected vertices
have the same color.
Identify a significant optimization in this encoding. Hint: Can any constraints be dropped? Why?
If the constraints are not already in CNF, specify them in CNF now. For
$N$ vertices, $K$ edges, and $M$ colors, how many variables does the optimized
encoding require? How many clauses?

As suggested by @D.W.♦, I copy the original problem here (above is the version simplified by me). This original version is Exercise 1.6 from:

  Bradley, A. and Manna, Z. (2007). The Calculus of Computation. Dordrecht: Springer, p.34.

My Analysis

The optimized CNF within my ability is to use propositional variable $P_v^c$ to indicate that $\text{color}(v) = c$. Here we can only use at most $|V|$ colors of all colors, i.e., the number of colors in our design of propositional variables is $|V|\min (|V|, |C|)$. Then we can build a CNF: $$F_0 = \bigwedge_{v \in V} (\bigvee_{c \in C} P_v^c) \wedge \bigwedge_{v \in V} (\bigvee_{c_1 \not= c_2 \in C} (\neg P_v^{c_1} \vee \neg P_v^{c_2})) \land \bigwedge_{c \in C \\ \langle v, w\rangle \in E} (\neg P_v^c \vee \neg P_w^c)$$

In this variable, there're $|V| \min (|V|, |C|)$ propositional variables and $2|V| + |C||E|$ clauses.

I failed to prove $F_0$ is the CNF with neither the least propositional variables nor the least clauses. Is there an another CNF $F'$ with less propostional variables or less clauses? How to find the minimal number of propositional variables and clauses of legal CNFs?


texts: Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?

texts:
Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL?
The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence I am not sure whether its DCFL or CFL.

Can you provide an explanation that shows $L$ is either DCFL or CFL?

i dont know how to use math,i searched for the solution but didn't got any,my DPDA is shown in picture below.


texts: Compound interest with varying compounding frequency

texts:
Here is the problem I have attempted to solve.

  Given original principal $n$ and aggregate rate $r$, find the maximum final principal that can be yielded.

Though I know that the higher the compounding frequency is, the higher the final principal will be, a special condition applies:

  Intermediate principals are rounded down to the the nearest integer each time.

So for example $n = 10000$ and $r = 3$, I can choose to have

1% growth 3 times
a 2% growth then a 1% growth
or a 3% growth.

For case 1 n would grow as 10000 -> 10100 -> 10201 -> 10303.

For case 2 n would grow as 10000 -> 10200 -> 10302.

For case 3 n would grow as 10000 -> 10300.

So in this case the highest value would be 10303.

As another example, take $n = 10$ and $r = 10$. As it will not yield any changes to $n$ unless the growth rate is higher than 10%, the answer is 11.

So in mathematical terms it is to find $\max n\prod(1+r_i\%)$ where $\sum r_i = r$ with the rounding condition.

What I was trying to do is to find the minimum growth rate that would result in a change in $n$ and apply it immediately, then repeat the process until $r$ is used up, but it doesn't seem that it is getting the desired answer. Any hints would be appreciated. If you need any clarification please tell me.

    while(r > 0 && rate < r){
        rate++;
        if (n * (100 + rate) / 100 != n){
            n = n * (100 + rate) / 100;
            r -= rate;
            rate = 0;
        }
    }

$r_i$ must be positive integers.
This problem is adapted from A028:武器の強化 problem, which can be found here (on paiza, which is a Japanese-language coding contest site).


texts: "Functional dependencies" with cardinality constraints

texts:
Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\bigwedge_{i = 1}^k A_i = a_i} R\right\rvert \le n$ (and $A_i$, $B_j$ are attributes from the schema of $R$), i.e, for any choice of values for the attributes $A_i$ at most $n$ corresponding tuples of values for $B_j$ can be found in $R$. Then $\{A_1, \ldots, A_k\} \rightrightarrows^1 \{B_1, \ldots, B_m\}$ is just the functional dependency $\{A_1, \ldots, A_k\} \rightarrow \{B_1, \ldots, B_m\}$, and $\emptyset \rightrightarrows^n \{B_1, \ldots, B_m\}$ is an upper bound on the number of possible $B_j$-tuples occurring in $R$ (regardless of any selection).

One may come up with a bunch of possible inference rules similar to Armstrong's axioms, for example

reflexivity: $\mathcal{A}' \subseteq \mathcal{A} \implies \mathcal{A} \rightrightarrows^1 \mathcal{A}'$,
augmentation: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \implies \mathcal{A} \cup \mathcal{C} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C}$,
transitivity: $\mathcal{A} \rightrightarrows^{n_1} \mathcal{B}$, $\mathcal{B} \rightrightarrows^{n_2} \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n_1 n_2} \mathcal{C}$,
decomposition: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n} \mathcal{B}$, $\mathcal{A} \rightrightarrows^{n} \mathcal{C}$,
composition: $\mathcal{A}_1 \rightrightarrows^{n_1} \mathcal{B}_1$, $\mathcal{A}_2 \rightrightarrows^{n_2} \mathcal{B}_2 \implies \mathcal{A}_1 \cup \mathcal{A}_2 \rightrightarrows^{n_1 n_2} \mathcal{B}_1 \cup \mathcal{B}_2$.

Indeed, by setting $n = n_1 = n_2 = 1$, we obtain Armstrong's axioms.

Let $\Sigma = \{\mathcal{A}_i \rightrightarrows^{n_i} \mathcal{B}_i\}_{i = 1}^N$ be a set of such "cardinality constraints". Again following the conventions from functional dependencies, let us write $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$ if $\mathcal{A} \rightrightarrows^n \mathcal{B}$ holds in every relation $R$ where all constraints in $\Sigma$ hold. Let $\min_\Sigma(\mathcal{A}, \mathcal{B})$ be the smallest $n$ such that we have $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$. How can we compute (or bound) $\min_\Sigma(\mathcal{A}, \mathcal{B})$? Is there a way to minimize $\Sigma$ and obtain (the smallest) $\Gamma$ such that $\min_\Gamma(\mathcal{A}, \mathcal{B}) = \min_\Sigma(\mathcal{A}, \mathcal{B})$ for all sets of attributes $\mathcal{A}$, $\mathcal{B}$?

I'd be interested in references or algorithms regarding the constraints defined above. Have they been studied? What is the standard terminology or notation?


texts: Rank operation in search tree, number of nodes between 2 values

texts:
What kind of search tree should I use in which I will have operation Rank[x, y] which will return number of existing nodes/values between x and y in time O(depth of tree) so the operations find, insert and delete will have also time complexity O(depth of tree)?
I was thinking about a-b tree, which has find, insert and delete in O(log n), but I do not know how should I implement the rank operation. I was thinking to add each value in node information about number of its children but it wont be in O(log n) time.


texts: Can you give me insight into the time and space complexity of those pairing functions?

texts:
I am looking for a pairing function with linear time complexity.
I found

one in Steven Pigeon's thesis (p 115, §5.3.6.3) described in English on MathOverflow that works by bit interleaving.
another from Regan's 1992 paper (p 289, last paragraph) that works by bit concatenation based on a state machine.

The one from Pigeon seems $O(1)$ in space and $O(n)$ in time to me, assuming fixed-length datatypes (int64). Space $O(1)$ would derive from the fact that
$bitlength(z) = 2*max(bitlength(x),bitlength(y))$
$O(n)$ time seems to trivially derive from the absence of any operation apart from bit interleaving, which is $O(1)$ for each pair of bits.
What bugs me is that in Regan (1992), the algorithm is more involved but claims identical time and space complexity. I guess I am misunderstanding something.
Is the Pigeon function really $O(n)$ in time? If the problem of integer pairing has such a simple solution, how come Cantor's and the Rosenberg-Strong pairing functions are cited so widely while having inferior performance characteristics?


texts: Which machine learning algorithms can be used for time series forecasts?

texts:
Currently I am playing around with time series forecasts (specifically for Forex). I have seen some scientific papers about echo state networks which are applied to Forex forecast. Are there other good machine learning algorithms for this purpose?

It would also be interesting to extract "profitable" patterns from the time series.


texts:
If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable?

My reasoning is, that we have a finite sets of moves  and since all finite languages are decidable and at some point x is going to get y this problem is decidable. What do you think?


texts: Why is the lower bound of element uniqueness in $\Omega(n\log n)$?

texts:
I wish to discuss the element uniqueness problem. First let's define the problem:

Definition from wikipedia:

  In computational complexity theory, the element distinctness problem
  or element uniqueness problem is the problem of determining whether
  all the elements of a list are distinct.

i am aware that this question has been asked before, however, I am confused about what lower bound actually means.

Let's say we are given an arbitrary array of integers. We could simply use hashing to check for element uniqueness. Hashing works in amortized $O(1)$ time. Hence, shouldn't the lower bound of element uniqueness be $\Omega(n)$?

Am I understanding lower bound wrongly? Does lower bound mean an asymptotic lower bound for general cases (i.e. we could have arrays of strings as well) or does it apply to all cases?


texts: Relationship between Kleene Star of a subset of regular language and the regular language

texts: If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?


texts:
In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing machine (QTM) that can actually benefit from quantum effects, namely, perform on high-dimensional systems?


texts: How to convert a search solution to a path to be tracked?

texts:
Let's say I have a space with obstacles and I'm trying to control a robot's movement while avoiding obstacles. I also have a start state and a goal state. I use a search algorithm to find the shortest path from the start state to the goal state (actually I really don't care if the path is optimal or not at this stage, I just have a path and I want to follow it).
So the path is actually an array of actions, [up, up, left, ...]. I was wondering how should I convert this array of actions to a real path to be tracked by a robot?

Should it be just an array of waypoints? Or I could generate a smooth path from this array of actions?

The path is an array of actions that you could use and get an array of points in the working space. How should one convert these points into a path which is a function of time  i.e. convert the result of a search algorithm into a control problem such that I have a desired path and now I have to design a controller for the robot to follow that path.

The way I've implemented the search algorithm I'm getting a series of up/left/... commands as the output. It's easy to convert this array of commands to a set of points but I'm not sure on how to convert this set of points to a path. Once I have a path it's relatively easy to design a controller for a robot to follow it. Right now I'm just looking for methods on how to convert this points to a path. I've found a report with extensive details on how to use splines and generate a path. But it would be great if I could find other methods and compare them.

Just as an example of what I'm looking for, if I have:

x(t) = sin(2t);
y(t) = cos(6t);

I have to design a controller for the robot to follow this path:

Now, my question is what methods there are to generate such paths which also take into account the constraints on movement of the robot. I hope the question is more clear now.

I've found a great report on how to convert a set of points to a smooth path using splines but I would appreciate if someone could give some information on other available methods.


texts: Finding all subsets of a set of MultiSets made of elements from a single MultiSet (without replacement)

texts:
(originally asked on StackOverflow)

Two recent questions on StackOverflow by the same author1 are generally solved by the same technique.  This feels to me like it would be a studied and perhaps well-solved problem.
I would like to know what it might be called and where to find more information about it, assuming it is a well-known problem
This is my own phrasing of the question:
If we have a Set, $M$, of MultiSets, $M_1$ - $M_n$ made up of elements of Set $S$, and we have a MultiSet of components, $C$, also drawn from $S$, how do we find all subsets of $M$ such that the for each subset, the multiplicities of each element of $S$ in its union is no greater than the multiplicity of that element in $C$ ?2
For example, paraphrasing my own answer to the first question:

I think I understand that what you want would be for something like this:
const catalog= ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]
const components = ["a", "b", "a", "c", "d", "e"]

simultaneousItems (catalog, components)

to yield
[
  ["ad", "ace"], ["ad", "ba"], ["ad"], ["aab", "cd"], ["aab"], ["ace", "ba"],
  ["ace", "bd"], ["ace"],["cd", "ba"], ["cd"], ["ba"], ["bd"], []
]

where every array in the result is subset of catalog items that can be made together out of the components supplied.  So, for instance, none of the output arrays contains "adf" or "def", since we have no "f" in the components, and none of them contain both "ad" and "aab" since we only have two "a"s in the component list.

Note that I'm using "abc" as a shorthand for the set containing the strings "a", "b", and "c".
The original problems seemed to be looking for maximal subsets, so there is one additional step, and that is perhaps an equally interesting problem, but I'm more curious about the version above.
Please don't look at my solution as any sort of algorithmic ideal.  It was the first idea that came to mind.
Is this a well-known problem?  There's some vague relationship to the Knapsack problem, and other packing problems, but I can't quite figure out what and where to search.

1 The first one is closer to what I think is the fundamental algorithmic question.  I'm assuming the second one is closer to the real problem the OP is trying to solve.  Without any feedback yet from the OP, I don't know for certain that my answers match the real need, but I find this an interesting question regardless.
2 More explicitly (and forgive me for being too far away from formal Math classes) if $C$ = ${\{S_1^{m(z_1)}, S_2^{m(z_2)}, ... S_j^{m(z_j)}\}}$ for some integer $j$, and $S_1$, $S_2$, ... $S_j$ in $S$, and if $N$ = ${\{M_{a_1}, M_{a_2}, ... M_{a_k}\}}$ is one of the subset of $M$ in the result, and ${∪\{{M_{a_1}, M_{a_2}, ... M_{a_k}}\}}$ = ${\{S_1^{m(x_1)}, S_2^{m(x_2)}, ... S_j^{m(x_j)}\}}$, then for all $i$, $x_i$ ≤ $z_i$.


texts: What complexity class is this set of grammars? In between NL and P?

texts:
Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

What complexity class does this correspond to?

It appears to be the problem of finding an "all-in-path" in a "3-digraph" (See: Is there a name for this directed graph and path concept? 3-digraph and all-in-path?).

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars?

What complexity class is this set of grammars? RE?


texts: How to calculate the miss ratio of a cache

texts:
I know how to calculate the CPI or cycles per instruction from the hit and miss ratios, but I do not know exactly how to calculate the miss ratio that would be 1 - hit ratio if I am not wrong. I know that the hit ratio is calculated dividing hits / accesses, but the problem says that given the number of hits and misses, calculate the miss ratio.

My reasoning is that having the number of hits and misses, we have actually the number of accesses = hits + misses, so the actual formula would be:

  hit_ratio = hits / (hits + misses)

So the miss ratio would be

  miss_ratio = 1 - hit_ratio

If my reasoning is correct, right?

What is the hit and miss latencies? Because I need them to calculate the mean access time using the hit and the miss ratios and the hit and the miss latencies (in cycles)...


texts: Analysis of a LALR shift-reduce conflict

texts:
I have created an extremely simple byacc grammar (ok, it's not really that simple but I simplified purposefully to be a minimal complete verifiable example):

%token NEWLINE SPECIFIER
%token EQUALS STRING VAR

%start st

%%

st: toplevel;

toplevel:
| toplevel VAR EQUALS STRING NEWLINE
| toplevel list NEWLINE
;

list:
  maybe_specifier VAR
| list maybe_specifier VAR
;

maybe_specifier:
| SPECIFIER
;

However, it is warning about a shift-reduce conflict. If I remove maybe_specifier from the grammar entirely (so that variables cannot be prefixed by a specifier in a list), the conflict disappears. Similarly, if I remove the variable assignment from the grammar entirely, the conflict disappears too.

My questions are:

Where does this shift-reduce conflict come from? Is it an artifact of LALR? Or would it be there even with an LR(1) parser generator?
Does this shift-reduce conflict matter? Or is it always doing the right thing anyway by using shift instead of reduce?
Is there any way to modify the grammar to accept the same language without having the shift-reduce conflict, other than by prefixing VAR in assignment line by maybe_specifier and then checking whether the SPECIFIER was there in a semantic action, and failing if the SPECIFIER was present?

My current approach is to modify the assignment rule to initially accept a SPECIFIER in the form of maybe_specifier but then terminate with a parse error if the SPECIFIER was there. I'm wondering if there's a cleaner approach that would allow me to do the same without adding a semantic action.


texts: What additional expressivity does polyvariance give in pushdown CFA?

texts:
I'm reading through Pushdown Control-Flow Analysis of Higher-Order Programs, which presents a synthesis of the Abstracting Abstract Machines technique and pushdown automata to get static analysis which perfectly matches call and return sites. The paper presents a monovariant and two polyvariant forms of the system.

I can't seem to get my head around what additional expressive power polyvariance (e.g. 1CFA) grants when return-flow merging is already eliminated in the monovariant case by the pushdown methods.

Could someone provide an example program in which polyvariance helps?


texts: Algorithms to prioritize equipment renewals

texts:
I am looking for algorithms to prioritize equipment renewals.

Input: (years since last renewal, cost of renewal, importance of renewal).

Output: An ordering of the equipment according to which it will be renewed.

I do not know if there are any algorithms for this particular problem. If you have any idea how to fit this problem into a more general context, that would be useful too.

A way to rephrase the problem:

You have $n$ pieces of equipment $E_1,\ldots,E_n$. For each piece $E_i$ you have a triple $(\text{age}_i,\text{cost}_i,\text{importance}_i)$. At the beginning of the year you have $X$ amount of money. You want to spend these money in order to minimize the function $\sum_i \text{age}_i\cdot \text{importance}_i$ at the end of the year. So, during the year you have to select a subset $S$ of $\{1,\ldots,n\}$ such that:
$$\sum_{i\in S} \text{cost}_i\le X \text{ (cost constraint)}$$ and the sum $$\sum_{i\in S} \text{age}_i\cdot \text{importance}_i$$ is maximal among all subsets of $\{1,\ldots,n\}$ that satisfy the cost constraint.

Any help?


texts:
This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to complete.  Then this computer can do an infinite number of calculations in a finite amount of time.

Why is this impossible?  Is there a lower bound on how long it takes to carry out a non-trivial calculation?


texts:
I'm studying the concurrency in programming and the atomic instructions.
What i have not understood is the concept of "fairness" applied to this matter.
Can you give me an hint ?


texts: Job scheduling with a bottleneck problem

texts:
Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete.

Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a time and both phases require 1 unit of time. After being pre-processed, job $J_i$ is sent to a machine with unlimited power (that can handle in parallel an unlimited number of jobs) and it will be ready in time $T_i$, then it must be sent (immediately) to machine M again for post-processing.

The associated decision problem is:

Input: the processing times $T_i >0, T_i \in \mathbb{N}$ of $N$ jobs, an integer $K\geq 2N$
Question: can we process all the jobs in time $\leq K$ using the above "bottleneck" model ?

Has this problem a name?
What is its complexity? (is it in $\sf{P}$ or is it $\sf{NP}$-complete?)

UPDATE 29 March:
As correctly noticed by M.Cafaro in his answer, the problem is similar to the
Unconstrained Minimum Finish Time Problem (UMFT) (see Chapter 17 of
Handbook of Scheduling Algorithms) which is $\sf{NP}$-hard (proved in
 W. Kern and W. Nawijn, "Scheduling multi-operation jobs with time lags on a single machine", University of Twente, 1993). As I can see, there are some differences because in my model:

the pre/post processing time is constant (1 unit of time)
as soon as the job is completed it must immediately be post-processed (the UMFT model allows delays)

I didn't found the Kern & Nawijn proof online, so I still don't know if the above restrictions change the difficulty of the problem.

Finally you can think the whole process like a single cook robot with a big oven; the robot can prepare different types of foods one at a time (all require the same time of preparation), put them in the oven, and as soon as they are cooked it must remove them from the oven and add some cold ingredients ... the "cook robot problem" :-)


texts: Simplest way to check edge set for transitivity

texts:
I'm playing around with tournaments and currently have the problem that I need to check whether a given subset of the edges of a tournament is transitive (it need not be acyclic). I'm aware that I can always take the transitive closure of the edge set and see whether it terminates without adding a single edge or not, but I was wondering if there might be a simpler way than that.

Note that I'm specifically going for simplicity, not efficiency; the tournaments I want to check are over a maximum of $7$ vertices, so complexity really isn't an issue. I would prefer simple, easy to implement ways. The simplest I could find so far is Floyd-Warshall, but maybe someone knows anything that's simpler still.


texts: Counting number of paths between two vertices in a DAG

texts: I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.


texts: What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

texts:
I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms:

When the same heuristic information is given to all the algorithms.


texts: Do correlated inputs imply existence of efficient communication protocols?

texts:
Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such as disjointness of $X$ and $Y$ requires $\Omega(n)$ bits assuming the input distributions of $X$ and $Y$ are chosen to be "hard".

Now suppose that we know that $H(X | Y) = k$ and $H(Y | X) = k$, for $k << n$. Is it always possible to derive an efficient deterministic communication complexity protocol (that computes a given function $f$) and has communication complexity at most $O( H(X | Y) \cdot H(Y | X) )$ ?

If the answer to the above question is no, is there an easy counterexample, i.e., a function that requires a high amount of communication despite correlated inputs?

One approach I was thinking about is that, since Alice knows $X$ and $H(Y | X)=k$, we could in advance fix an enumeration $E_X$ of the possible choices of Bob's input $Y$, given $X$.
Clearly, the choice of a specific $Y=y$ from $E$ can be described using $k$ bits.
But this doesn't seem to help at all: Bob doesn't know $X$, so he doesn't know which enumeration $E_X$ is used by Alice (and vice versa).


texts:
From Kozen's Automata and Computability, 3ed, lecture 32 p. 328:

What are HP and MP in this context?  I tried looking around and this text says:

How did the halting problem and membership problem become regular expression?  I am so loss here.


texts: Does XNOR of three variable equals XOR of same three variables

texts:
I came across following excerpt:

  $(x'y'+xy)'z'+(x'y'+xy)z=x\oplus y\oplus z$

What I see is left hand side is XNOR of $x,y$ and on right, $z$ and I get XOR of of $x,y$ and $z$ !!!
In other word,

  $XNOR(XNOR(x,y),z)=XOR(XOR(x,y),z)$

Somehow I am surprised by the result, as I didnt came across this earlier, no text stated this explicitly and was unexpected.
It was unexpected because, I knew some other equalities and inequalities stated below, so was never thought of existence of above equality.

  $XNOR(x,y)=NOT(XOR(x,y))$
  $NAND(NAND(x,y),z)\neq AND(AND(x,y),z)$
  $NOR(NOR(x,y),z)\neq AND(OR(x,y),z)$

Q1. Am I interpreting it correct as XNORs of three variables equals XOR of same three variables?
Q2. If yes, can someone shed more light about why such relationship is not true for other gates? Is just that their definition does not permit such relationship? Or Is it beacause ExOR is not basic gate, while AND and OR are?

PS: Sorry for naive, possibly stupid question.

The full excerpt:

  $(x'y'+xy)'z'+(x'y'+xy)z$
  $(x'y')'(xy)'z'+x'y'z+xyz$
  $(x+y)(x'+y')z'+x'y'z+xyz$
  $xy'z'+x'yz'+x'y'z+xyz$
  $=x\oplus y\oplus z$


texts: Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?

texts:
Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from the completeness and soundness theorems, which equate VALIDITY and THEOREMHOOD, the latter being the problem of finding a proof for a formula, which had previously been shown to be recursively enumerable.

However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?

Note: this question refers to first-order logic without arithmetic, so Gödel's Incompleteness Theorem does not have a bearing here.


texts: In a DAG, does there exist a sink for all vertices in the DAG?

texts:
The following statement is considered true:

  In a DAG, for every vertex $v$, there exists a sink $s$ such that
  there is a path from $v$ to $s$.

However, my counter example to this is a binary search tree. The leaf nodes in a binary tree do not have a path from themselves to a sink. Hence, am I interpreting this statement incorrectly?


texts: Is Rice's Theorem equivalent to the Halting problem?

texts: As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like one could write a proof using that the Halting problem is undecidable to show Rice's Theorem. I'm not exactly sure how one would go about proving such a thing (though it seems by contradiction would be the natural thing to do), but it feels to me that that it should be possible?


texts: Help me understand whether these critical pairs are joinable

texts:
I have the following TRS $R$:
$$
  l_1 = f(g(x)) \to f(x) = r_1 \\
  l_2 = g(f(y)) \to g(y) = r_2
$$
I want to know if $R$ is confluent, and whether $g(f(f(x))) \leftrightarrow_R^* g(g(g(x)))$.
I have already proven termination.

I use the fact that $t = f(y)$ is a subterm of $l_2$ and can find a substitution $\sigma$ that unifies $t$ with $l_1$, namely $\sigma(y) = g(x)$.
This yields critical pair $\langle g(g(x)), g(f(x)) \rangle$.
I can use similar reasoning to unify $t = g(x)$ with $l_2$ and find critical pair $\langle f(f(y)), f(g(y)) \rangle$.
Now I wonder whether these critical pairs converge (i.e. whether they are joinable).
For example, I consider the former critical pair.
If I understand correctly, I need to find whether there exist a $v$ such that $g(g(x)) \to_R^* v \leftarrow_R^ * g(f(x))$.
However, I do not understand whether I can conclude that they are not joinable since $g(g(x))$ is in normal form and $g(f(x)) \to g(x)$, $g(x) \ne g(g(x))$, or, whether I can rename the second to $g(z)$ and unify.
Say, $g(z)\tau = g(g(x))$ for $\tau(z) = g(x)$ and conclude that the critical pair is joinable.

If they are joinable, then $R$ is locally confluent. By Newman's theorem, I have that $R$ is confluent, since $R$ is also terminating. But then $g(f(f(x))) \leftrightarrow_R^* g(g(g(x)))$ iff the normal forms of both side are equal.
Here I have the same problem, $g(g(g(x)))$ is already in normal form, and $g(f(f(x))) \to g(f(x) \to g(x)$. Strictly speaking these are not equal, or can I rename the latter (to $g(z)$) and conclude they are equal for a substitution $\tau(z) = g(g(x))$?


texts: Is this a good approach for first attempt to create my own language and compiler?

texts:
I want to try to create my own very simple programming language and it's compiler or interpreter.

The programming language I use is Java.

My idea was to create a compiler which will compile source code of my created language to some kind of intermediate code (nothing binary or complex, just plain text), and then have another program (a kind of virtual machine or interpreter) which will execute this intermediate code in Java.

For example, the 'programmer' types: write "hi world". The compiler turns it to some intermediate code like w-hi world. The VM/interpreter program reads this intermediate code and executes System.out.println("hi world");

My question is:

Is this approach common with programmers who want to try to create a simple language for the first time? Is this a good way to start?

I searched this site and came across questions on this subject, but the answers were more complex and technical than what I'm looking for.


texts: If problem A is logspace reducible to 2-SAT, is A in NL?

texts:
I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL?

If so, how does one formally go about proving that a language is in NL - is the only way we can do this by providing some deciding non-deterministic TM for A that only uses logspace?


texts: What is a the fastest sorting algorithm for an array of integers?

texts:
I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are:

Which is the fastest currently known sorting algorithm?
Theoretically, is it possible that there are even faster ones? So, what's the least complexity for sorting?


texts: Is induced subgraph isomorphism easy on an infinite subclass?

texts:
Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem

  Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?

is known to be in class $\mathsf{P}$?


texts: Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine

texts: The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part similarity to the PRAM model, but with additional features in state management, by communication, and synchronization. So, in a sense it implies barrier synchronization, communication, and concurrent communication implicit in its workings, with processors having an order imposed on them. Does this conflict with the Turing machine model(?). Can one simulate one model by the other? Are they equivalent, or are there differences between these models?


texts: Skolem constant in existential instantiation for first order logic

texts:
For any sentence $\alpha$, variable $v$, and constant symbol $k$ that
does NOT appear elsewhere in KB:
$$\dfrac{\exists \nu. \alpha}{\mathsf{subst}(\{ \nu / k \},\alpha)}.$$
E.g., $∃x. \mathrm{Crown}(x) \wedge \mathrm{OnHead}(x, \mathrm{John})$ yields

$\mathrm{Crown}(C_1) \wedge \mathrm{OnHead}(C_1, \mathrm{John})$

Provided $C_1$ is a new constant symbol (aka Skolem
constant)

Can someone clarify the Skolem constant concept?


texts: For what kinds of languages is min |NFA| = Ω(min |DFA|)?

texts:
Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that recognizes the given language). Write $|A|$ for the size (number of states) of the automaton $A$. In general, $|N(L)|$ can be a lot smaller than $|D(L)|$ (down to $\lg |D(L)|$, since determinization is exponential in the worst case).

I am interested in languages for which the minimal NFA is guaranteed to be at least a fraction of the size of the DFA: $|N(L)| \ge k |D(L)|$. What families of regular languages have this property? In other words, for what family of languages $(L_n)$ such that $|D(L_n)| = n$ is $|N(L_n)| = \Omega(n)$?


texts: How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the build_heap function in the book, but I don't get it.


texts: Computer vision: object detection with labels that are single coordinates

texts:
Are there papers in the literature that address the following object detection task ?

The task can be described as follows:

Given a set of images, the labels are just coordinates (x,y) that represent the object locations that we wish to detect. A coordinate is not necessarily at the centre of the object and the object can be of any size.
The task is to detect an object that is either a person, a boat, or a car. However, the labels do not state the category of the objects, the labels are simply coordinates that are close to the objects of interest.
The images are taken every hour and they are snapshots of the same scene; therefore, background subtraction techniques might help.
There are around 2000 images of the same scene and each image usually has 2 objects of interest.

I am wondering if such task has been approached before ?

Hog features and SVM have shown great success in detecting humans in images. But the relevant literature use training data where the objects of interest are labelled using a bounding box instead of a single coordinate.

The three main challenges are:

Choosing the bounding box for the classifier is difficult since objects can be of any size.
snapshots of the scene is taken every hour (camera can move slightly as well); so using background subtraction isn't straightforward.
we don't have much labelled data.

It would be interesting to see how people dealt with these challenges.

Thanks!


texts: How are artificial intelligence and Natural intelligence compared?

texts: I can remember reading that computer intelligence is heading (or maybe the most powerful ones already have) towards the Natural intelligence of a four-year-old child. But how are the two kinds of intelligence compared?


texts: What is the fastest way to merge two B trees?

texts:
Given two B-trees of some order $m$ -  $T_1,T_2$, such that $y > x$ for every pair $x \in T_1$ and $y \in T_2$.
What is the fastest way to create a new tree that is the union of both $T_1,T_2$?

My current solution is naive in a sense that I create an array and insert all $T_1$ elements, than all $T_2$ elements.
As a result I have a sorted array which I can create a new tree off of with a cost of $n \log n$

I'm thinking that there must be a better solution, something like the AVL merging question but I can't figure it out.


texts:
How would we find the three smallest elements in a list and return it as a tuple (a,b,c) using divide and conquer?
So far I've considered the following:
def sm(L):
    # base
    if len(L) == 3:
        return L sorted
    else:
        # divide

How would I divide the list so that we guarantee the list to be of size 3 and be in the base case?


texts: Simulating QC using nondeterministic Turing machine

texts:
Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine?

Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing machine?

I am not sure what are the relations between Turing Machine, Probabilistic TM, Non-deterministic TM and Quantum TM and how they will affect the simulation/emulation of a QC.


texts: Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?

texts:
Sanjeev Arora and Boaz Barak show the following :

  $P/poly = \cup_{c,d} DTIME (n^c)/n^d$

where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$  and runs in $O(n^c)$ time. I do follow the proof. But I feel the  proof only holds if we assume that  $\forall n$ the advice given to any two $n$ length strings $x$ and $y$ is same.

But I am unable to see if the theorem still holds if the above condition if not applicable ?


texts: Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

texts:
I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$.

For $n=1$ we trivially have a single (random) point.

For $n=2$ we have two sets of points $S, Q$ and we seek to find the (distance of the) closest pair of points $p, q$ such that $p\in S$ and $q \in Q$. I have also found an efficient algorithm for this, using voronoi diagrams.

For $n>2$ things get tricky. I have no clue where should I head to.  Let's say we have $x$ red, $y$ green and $z$ blue points laid down in an Euclidian plane. How do we find the minimum distance of a route passing for one red, one green and one blue point?

Is this some special case of the Traveling Purchaser Problem?


texts:
I am trying to create a generalised suffix tree from a very large number of strings using Ukkonen's algorithm, however I run out of unique symbols to use as string termination characters.

I was wondering whether there is any way to work around this problem? For example, would it be possible to mark string ends as integers and when the integer grows to a multi digit value, still interpret that value as a single character.

Any input would be appreciated,
thanks !


texts: Size of the data bus connecting CPU cache and RAM?

texts:
I'm reading about CPU caches and I read that typically, cache line sizes start from 32 bytes. Since memory is slower than CPU caches therefore data is frequently loaded from the RAM into the cache and the size of the data loaded depends on the cache line size.

Now I wanted to know what are the typical sizes of the data bus in between CPU caches and RAM in modern CPUs. Does this depend on the register size of CPU architecture or is it independent of that? Will a 32 bit CPU have a 32 bit data bus connecting the cache and RAM and a 64 bit CPU will have a 64 bit data bus? If it's true than am I right to conclude that if cache line size and RAM is similar then a 64 bit CPU should be about twice as fast as the 32 bit CPU? Because the data loading in cache will be faster.


texts: I am currently reading the Practical Byzantine Fault Tolerance paper. I am unable to completely understand the difference between 2f and 2f+1. If 2f+1 means that a majority of the nodes are non-faulty then what does 2f represent?


texts: What is the relation between word size and size of internal register of a processor?

texts: Is there any difference between word size and size of internal register of CPU ,since "Word size" refers to the number of bits processed by a computer's CPU in one go ,so does this imply that word size is architecture dependent and ALU register's size is same as word size ?


texts: How to calculate information gain in ID3?

texts:
I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A is given by:

Gain(A) = B(p/p+n) - Remainder(A)

where B is the entropy of a Boolean random variable and p and n are the number of positive and negative examples in the training set.

My question is:

do p and n always refer to examples in the full dataset, or the remaining examples in current partition of the set?

If the former applied, the value of B would remain fixed throughout the training procedure. Is this correct?


texts: Average length of s-t (simple) paths in a directed graph

texts:
Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices?

Relevant results on special graphs could also be helpful.


texts:
My algorithm-fu is really weak and I do not know how to express following problem in terms of any other problem known to me:

Given a small rectilinear grid and coordinates of four cells in this grid (let's call these cells A, B, C and D) find a shortest path which connects cells A => B => C => D (in this order, with no return back to A) so that each intermediate cell is visited at most once. Connections between cells can be only rectilinear (each cell can be connected only to the cells on its left/right/top/bottom).

Initially I thought of this problem as something similar to a wire routing on a PCB grid and searched for related algorithms, but all I found were optimal algorithms (Maze Runner, Lee) which usually described only networks with at most two connectors (or other extremely trivial cases), or algorithms which give non-optimal solutions (for example, Line Search).

Then I thought it might be possible to solve it with some path finding algorithm (A* with some fancy cost function, maybe) but I have no idea how to apply the requirements to such approach.

I think it might be something related to TSP, but I am not able to see this relation, nor even if I knew one, I do not know how to solve such problem in general. Note that I need an optimal solution, and even if problem is NP-hard (which I think it is), the problem size is guaranteed to be small enough for me to be able to find the asked path in a reasonable time.

I tried a few approaches:

For each permutation of {AB, BC, CD} find shortest path for each pair. But two problems here:

From all possible shortest segments connecting AB and BC, I do not know which one to pick, and the choice influences the shape of segments for remaining pair(s). I can try them all, but then:
I think (not sure tho) that solution might not include any shortest segment at all (i.e. final, optimal solution might consist solely of sub-optimal elementary segments). Am I right?

The only way I found to make problem easier is to limit the search to the bounding box of the cells of interest (with small adjustments if some cells are located on the same row/column or on an edge, then bounding box needs to be expanded by one or two cells).
Another approach that I thought of (did not try yet) is to apply following algorithm:

Remove all rows and columns from the grid which do not contain A, B, C nor D - this step would make the grid 'dense', so there would be no empty rows/cols between obligatory cells,
Calculate (possibly brute force with some DFS, or maybe even precalculate and hardcode) a solution for this reduced grid,
'Explode' this reduced solution by inserting empty rows and columns back, extending the connecting edges appropriately.
However, this algorithm is something I came up myself with, I have not tested yet, I could not find anything similar described anywhere (what makes me think it would not work ;) ), it's not supported by anything but just a desperate idea :)

Can this problem be expressed as a (possibly some special case of) TSP? If so, how can I reduce it so I could apply algorithms for solving this case of TSP? If not, what approach would you suggest?

EDIT: Below you can find two examples of non-trivial, tricky input (paths are added by me and I think they are correct ones, but maybe there are shorter ones I cannot see? ;) )

  0123456789     01234567
 ╔══════════╗   ╔════════╗
0║ B┐D A─┐  ║  0║A─┐D┐   ║
1║ ││└──┐│  ║  1║C┐└┐│   ║
2║ ││   ││  ║  2║││ ││   ║
3║ ││   ││  ║  3║│└─B│   ║
4║ │└───C│  ║  4║└───┘   ║
5║ └─────┘  ║  5║        ║
6║          ║   ╚════════╝
 ╚══════════╝


texts:
In context of "Computability", I have went over some proofs for Recursion
Theorem using Turing Machine description. A TM $M$ stands for a single tape
Turing machine and $\langle M \rangle$ is the description of TM $M$. Even some semi-decidable machines such as $A_{\mathrm{TM}} = \{ \langle M, w \rangle \mid \text{TM $M$ accepts $w$} \}$. My question is simple:

What is difference between using $\langle M \rangle,\langle w \rangle$ vs $\langle M , w \rangle$ for a TM description?

A simplistic answer I assume is that it is being a convention in writing formal proof that books follows standard of combining all inputs as a single description (all inputs comes under single brackets as opposed to multiple descriptions)?

My question c

If
$M_1 = \{ \langle M , w \rangle \mid \text{TM $M$ accepts $w$} \}$ and
$M_2 = \{ \langle M \rangle , \langle w \rangle \mid \text{TM $M$ accepts $w$}
\}$

What's the difference between $M_1$ and $M_2$?


texts:
Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$.
I am interested for a given NFA to compute a $n \times n$ simultaneous reachability matrix $R$, such that $R_{ij} = [\exists x : \{i, j\} \subseteq S(x)]$.
From NFA product construction of $F$ with itself and then checking the reachability from the starting state I can compute $R$ in $O(n^4 \cdot |\Sigma|)$ time. Is there a better algorithm?


texts: What is an example of a context-free language that runs in NP-time? I've done searches but cant find one. Frankly, I do not know how to determine when a CFL is P or NP. Can someone tell me, please?


texts: How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer

texts:
The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the match of the word in the search-buffer is the entire word in the look-ahead buffer? According to the desriptions I find, the algorithm matches as long as it can, and then outputs the offset, the length of the match and the next token after the matched portion in the look-ahead buffer, but in case the entire look-ahead buffer is matched we do not have a next token to output?

I nowhere find this case described, for example the pseudocode just states "X first char after p in view", but I am asking about the case where we have no char after p in the view, as p is entire view?

For example, consider a search buffer of size 5 and a look-ahead buffer of size 4 and we read in

|abrar|rarr|ad

then we find a match at offset 3, and the match (which extends behind the boundary between both puffers, but this is no problem) goes up to all of rarr, even the next a could be matched, but what we should do now, should we output (3,4, C(a)) where C(a) denotes the code of a which is not in the look-ahead buffer, or should we just match the first 3 tokens?


texts: Randomized algorithm for computing trapezoidal decomposition.

texts:
In the his paper A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons (Computational Geometry: Theory and Applications, 1:51–64, 1991), Siedel discusses following algorithm for finding out trapezoidation and query structure cost.

Generate a random order $s_1, s_2, \dots, s_n$ of the segments of $P$.

Generate $T_1$ and $Q_1$ [initialization].

for $h = 1$ to $\log^∗ n$ do
a. for $i = N(h−1) + 1$ to $N(h)$ do:
Insert segment $e_i$, producing $T_i$ and $Q_i$ from $T_{i − 1}$ and $Q_{S i − 1}$.
b. Trace $P$ through $T_{N(h)}$ to locate the endpoints of all $e_j$, for $j > N(h)$.

for $i = N(\log^∗ n) + 1$ to $n$ do:
Insert $e_i$, producing $T_i$ and $Q_i$ from $T_{i − 1}$ and $Q_{S i − 1}$.

The paper says that step 4 is similar to step 3a so why not run the step 4 from $i=1$ to $n$ and perform location of points $\log^*n$ times in step 3?
Any help is greatly appreciated.


texts: what type is the graph reduced from k-regular hypergraph?

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$. If each $|V| = 2$, H is a general graph.

The degree $d(v)$ of a vertex v is the number of edges that contain it. H is k-regular if every vertex has the same degree k.

My question is: If we reduce a k-regular hypergraph to a general graph by replacing each edge with a clique, then the resulted general graph is not of bounded degree (the degree of a vertex can be up to n-1 where n is the total number of vertices). However I think it must be a special type of graph, I cannot figure out which type it is.

If you can help me out here I'd really appreciate it.


texts:
Suppose we have a set E of entities. Each entity is described by a set P of binary properties (i.e. each element e of E has a defined true/false value for each element p of P).

|P| >> |E|

We now want to select a subset of fixed size (e.g., 10) of P that will enable us distinguish the elements in E as accurately as possible.

In extensions of this basic scenario, the properties could assume numeric values.

Has this problem been studied? Under what name?

A practical example: there is a set of 100 bacterial species that are characterized for the presence or absence of 1000 genes. We now want to select a subset of 10 genes that, upon typing of a novel sample, will tell us which bacterial species that sample represents.


texts: Recovering species from a phylogenetic tree

texts:
This question is based on Problem 2 from the 'Bioinformatics contest' of 2018.

Given a phylogenetic tree $T=(V,E)$ of $n$ vertices, in which some leaves are assigned an integer color $c$ from $[1,n]$, the task is to find a coloring of the vertices $C:V\rightarrow [1,n]$ such that the subtree induced by each color is convex, i.e. there is exactly one vertex that has no parent in the induced subgraph of that color. An equivalent formulation is that the subgraphs induced by each color must be connected.

We are given that there exist a coloring meeting these constraints (there may be multiple). What is an efficient algorithm to find such a coloring?

Biological interpretation: The idea is that we're only given that some taxa (leaves in the tree) are of the same species and we do know the full ancestor tree. The assumption of convexity of a species means that each species has a common ancestor of the same species. Of course, this information isn't always sufficient to reconstruct the whole tree, but it might recover significant parts.

BONUS: So far, this is only the first case of the problem given in the contest. Observe that the above definitions remain unchanged if we replace $T$ by a DAG $D$ with a single vertex without parent (=single source DAG). Is there an efficient algorithm that solves this problem on general single source DAG's or edge-cactus single source DAG's?


texts: Reduction from Vertex Cover to Polygon Cover

texts:
Polygon Cover:

Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$.

Output: True if and only if there exists a subset in $S$ of at most $k$ (not necessarily convex) polygons such that every point in $P$ lie inside some polygon in the subset.

I am trying to give a polynomial reduction from Vertex Cover to Polygon Cover.  However, I am struggling slightly.  My idea is that to construct the set of points $P$, I figured that I should map each $uv \in E$ with ($u < v$) to a point $(u, v)$.  For the set of polygons $S$, I was thinking to define some type of non-convex polygon in order to cover the rows and columns.


texts: Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

texts:
I was reading about cutting stock problem
https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-Bound and delayed column generation...
I read them but it all look same ...every case we break problem into sub problem

Can anyone shed some more light with some example.?


texts:
I know that P = PSPACE  is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME.

Is anything known about the relationship between PSPACE and NEXPTIME? What about under the assumption that P = NP or that P != NP? Are the containments open problems from PSPACE all the way to NEXPTIME?


texts: Lower-bounds of running-time for output sensitive Algorithms

texts:
Let me ask my general question using a specific example, namely range searching:

Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle.

If the rectangle contains $k$ points, then this can be solved in $O(\log n + k)$ time (after some preprocessing). I understand that this is in some sense optimal, but what if the points obey some regularity?

Obviously if they are from the integer grid, this can be solved in constant time.

What is less obvious to me is the situation where the points lie equally spaced on some complicated curves: I could report to the user a set of curve-intervals tuples from which he can deduce the number of points.

But am I actually still solving the problem, or am I just outsourcing the work to the user?

I realize that the question is not very precise and I am not sure if such topics have been studied before.
I would be interested in any literature reference, where algorithms produce output in a non-explicit way.


texts:
My understanding is that computers are basically made of nand gates, and that all other gates, such as and, or, etc, can be made from nand gates.

So far so good, but how do we get from nand gates to the things we actually interact with when we program computers, such as numbers, strings, and even collections of things?

For example, how is the binary number 1011 represented in nand gates?


texts: Find a sorting procedure for seven elements that minimises the average number of comparisons performed

texts:
In The Art Of Computer Programming, Volume 3, Chapter 5.3.1, Problem 26, Knuth asks one to construct a sorting method that achieves the minimum number of average comparisons for n=7. This means that one needs to find a sorting tree that minimises the total length of all paths from root to every leaf (also known as external path length). A leaf node represents one of the n! permutations of n elements. The average number of comparisons over all possible inputs (all n! permutations) is then simply the external path length divided by n!. The minimal external path length for n=7 is known to be 62416, due to L. Kollar, "Optimal sorting of seven element sets", 1986. Kollar does not seem to construct a sorting tree that achieves this, he only shows that one cannot do better than 62416. Does anyone know whether such a sorting tree has been constructed or is it still an open problem?

Secondary question. How many comparisons does the best known method achieve for n=8? The lower bound for n=8 is 619904, but it is not known if it is obtainable.


texts: Does overclocking a cpu speed up a poorly optimised process?

texts:
Perhaps this isn't exactly a computer science question, but I thought this wouldn't strictly fit in Electrical Engineering either. Let me know if I should move this somewhere else

Suppose I have a process that is single-threaded and rather poorly optimised. It doesn't max out my processor, and instead stays stuck at around 20% usage. Would overclocking my CPU even really affect the running speed?


texts: Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say that $P_2$ is NP-complete?


texts: How to solve the following problem by using Gaussian elimination with partial pivoting (A=PLU)?

texts:
****The Question is here***** (in the link)

Given a nonsingular matrix A $\in$ $R^*(nxn)$, how would you solve the following problems efficiently using Gaussian elimination with partial pivoting (the same as A = PLU)?

(a) Compute $\alpha$ = $c^T$(A^-1) b, where c, b $\in$ $R^n$

(b) Solve AX = B, where X, B $\in$ $R^*(nxm)$

for (a), I have no idea on what the equation is and
for (b), I solve as the following but I am not sure does it applied to all X where it can be come from any n x m matrix

AX=b, PLUX=b, LUX=P^(-1)b, Ly = P^(-1)b where Ux = y.

So can anyone tell me how to solve (a) and verify my answer for (b)? Thanks!


texts: Checking whether a number is a square or higher power modulo n

texts:
Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know?  Is the Jacobi symbol helpful?

What about higher powers, e.g., testing whether $x$ is a $k$th power modulo $n$?


texts: What exactly is the LL(k) grammar condition?

texts:
I have a bit of trouble understanding the definition of LL(k) grammars.

Here it's defined as:

  for every pair of production rules
  $A\rightarrow
α$
   and
  $A \rightarrow
β$
   the following condition holds.
   $\text{FIRST}_k$
  (
   $\text{α FOLLOW}_k$
  (A)) $\cap$
   $\text{FIRST}_k$
  (
   $\text{β FOLLOW}_k$
  (A))
  $=\emptyset$

What does this mean concretely? What is the subscript $_k$?
Why is it for a "pair of production rules"?


texts:
Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.
Of course, when we talk about red-black trees*(see definition at the end) being balanced, we actually mean that they are height balanced and in that sense, they are balanced.
Suppose we try to formalize the above intuition as follows:

Definition: A Binary Tree is called $\mu$-balanced, with $0 \le \mu \leq \frac{1}{2}$, if for every node $N$, the inequality
$$ \mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$$
holds and for every $\mu' \gt \mu$, there is some node for which the above statement fails. $|N_L|$ is the number of nodes in the left sub-tree of $N$ and $|N|$ is the number of nodes under the tree with $N$ as root (including the root).

I believe, these are called weight-balanced trees in some of the literature on this topic.
One can show that if a binary tree with $n$ nodes is $\mu$-balanced (for a constant $\mu \gt 0$), then the height of the tree is $\mathcal{O}(\log n)$, thus maintaining the nice search properties.
So the question is:

Is there some $\mu \gt 0$ such that every big enough red-black tree is $\mu$-balanced?

The definition of Red-Black trees we use (from Introduction to Algorithms by Cormen et al):
A binary search tree, where each node is coloured either red or black and

The root is black
All NULL nodes are black
If a node is red, then both its children are black.
For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Note: we don't count the NULL nodes in the definition of $\mu$-balanced above. (Though I believe it does not matter if we do).


texts: algorithm for finding a straight line to separate class

texts:
I want create algorithm, which find a straight line which will separate the most objects from the class. The line must be parallel to the X or Y axis. Example:

Above example present two class: circles filled and unfilled. Red line is a solution to the problem. Has anyone the idea how to find such a simple?


texts:
I'm a person using english as the second language and reading CLRS book at a slow pace due to my poor english. I have a problem with understanding the meaning of the word 'alternative'. In page 303 on CLRS, says:

  we should convince ourselves that exhaustively checking all possible parenthesizations does not yield an efficient algorithm.Denote the number of alternative parenthesizations of a sequence of n
  matrices by P(n). Since we can split a sequence of n matrices between
  the kth and (k+1)st matrices for any k = 1,2,...,n-1 and then
  parenthesize the two resulting subsequences independently, we obtain
  the recurrence ...(omitted)

What is the word 'alternative parenthesizations'? is this word equivalent to the 'all possible parenthesizations' in the above block quote? searching dictionary for the word 'alternative' is not helpful to me.
Thank you in advance.


texts:
Let's denote $IS(G)$ to be the size of the maximal independent set in $G$.
Consider the following language:
$$A = \left \{  G\ |\ IS(G)\ge \frac{1}{5}n \right \}$$

I know that $gap-IS [1/8 + \varepsilon , 1/4-\varepsilon]$ is $NP$-hard.

How can I infer that $A$ is $NP$-hard by utilizing the gap problem?


texts: Comparing two algorithms for all-pairs shortest paths

texts:
I read in my notes:

If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, and if we run Bellman–Ford algorithm $|V|$ times, we get time $O(V^2E)$.

The above details are not important.
I read too, that Dijkstra's algorithm works better for sparse graph, that is, $O(VE+ V^2 \log V)$ is better than $O(V^2E)$ asymptotically for sparse graphs.
I think sparse graphs are graphs satisfying $ |E| = O(V)$  or $E=o(V^2/\log V)$. In fact, I have two misunderstandings:

Which one is more common as the definition of a sparse graph?

According to 1, how we can intuitively understand that $O(VE+ V^2 \log V)$ is better asymptotically than $O(V^2E)$? At least I think the reverse is true.


texts:
Given $a,b,c,d \in \mathbb N$ and $b,d \notin \{0\}$,

$$
\begin{eqnarray*}
\frac a b < \frac c d &\iff& ad < cb
\end{eqnarray*}
$$

My questions are:

Given $a,b,c,d$

Assuming we can decide $x < y \in \mathbb Z$ in $\mathcal{O}(|x| +|y|)$, is there any way of deciding $ad<cb$ without having to preform the multiplications (or divisions), $a\cdot d$ and $c \cdot b$. Or is there some sort of proof that there is no way.
Is there a faster method to compare rational numbers than multiplying out the denominators.


texts: Lambda calculus : what about the bound variables in substituting expression?

texts:
I found the following set of lemma in my lambda calculus textbook :

  Lemma 1.16 Let $x, y, v$ be distinct (the usual notation convention), and let no variable bound in $M$ be free in $vPQ$. Then

  (a) $[P/v][v/x]M \equiv [P/x]M$ if $v \notin \mathrm{FV}(M)$;

  (b) $[x/v][v/x]M \equiv M$ if $v \notin \mathrm{FV}(M)$;

  (c) $[P/x][Q/y]M \equiv [([P/x]Q)/y][P/x]M$ if $y \notin \mathrm{FV}(P)$;

  (d) $[P/x][Q/y]M \equiv [Q/y][P/x]M$ if $y \notin \mathrm{FV}(P), x \notin \mathrm{FV}(Q)$;

  (e) $[P/x][Q/x]M \equiv [([P/x]Q)/x]M$.

In the first lemma , the first stage of substitution can be done because $x$ is a free variable in $M$ and and no variable bound in $M$ is free in $V$. But what about variables which are free in $M$ but bound in $V$? In that case, the substitution would carry the risk of changing the semantics, like if there were a free variable in $V$, let's say $K$, and there were a term in $M$ like $\lambda.k$ then it would definitely make $K$ a bound variable in $M$ if the $X$ being replaced is at a position right to the  $ \lambda .k$ and the substitution will be wrong.

How is this resolved? I am unable to see through this clearly.


texts: Computational complexity in Boolean network

texts:
An Boolean control networks can be expressed as
\begin{equation}
\label{ControlBN}
\left\{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ {x_{2}(t+1)=f_{2}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ {\vdots} \\ {x_{n}(t+1)=f_{n}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ \end{array}\right.
\end{equation}
where $x_i,~i=1,\dots,n,$ are state nodes, $x_i(t)\in\{0,1\},\,i=1,\cdots,n$ are the value of the state node $x_i$ at time t.  $u_i,~i=1,\dots,m$ are control nodes,  $u_i(t)\in\{0,1\},\,i=1,\cdots,m,$ are the value of the state node $u_i$ at time t, and $f_i:\{0,1\}^{n+m}\rightarrow \{0,1\},\,i=1,\dots,n$ are Boolean functions.
Consider the above system, Denote its state space as $\mathcal{X}=\{(x_1,\cdots,x_n)|x_i\in\{0,1\},i=1,\cdots,n\}.$
Given initial
state $x ( 0 ) = x^0\in \mathcal{X}$ and destination state $x^d\in \mathcal{X}$. Destination state $x^d$ is said to be reachable from the initial state $x^0$ at time $s>0,$ if there exists a sequence of controls $\{u(t)|t=0,1,\cdots,s-1\}$, where $u(t)=(u_1(t),\cdots,u_m(t))$,  such that the trajectory of the above system with initial value $x^0$ will reach $x^d $ at time $t=s.$
The above system is said to be controllable,  for any $x^0,x^d\in \mathcal{X},$ $x^d$ is reachable from $x^0.$
$M$-step Controllability Problem is defined as
Input: Given an Boolean Control Networks with $n$ state variables $x_1,\cdots,x_n,$ $m$ controls $u_1,\cdots,u_m,$ Boolean function $f_1,\cdots,f_n:\{0,1\}^{n+m}\rightarrow \{0,1\}.$ Given constant $M.$
Problem: for any destination state $x^d$ and initial state $x^0$, whether or not there  exists a sequence of controls $\{u(0),\cdots,u(M-1)\}$ such that $x^d$ is reachable from $x^0$?
In order to solve this problem, I convert the problem into logical form as following:
\begin{equation*}
\begin{split}
&\forall x_1(0)\cdots\forall x_n(0)\forall x_1(M)\cdots\forall x_n(M)\exists u_1(0)\cdots\exists u_m(0)\exists x_1(1)\cdots\exists x_n(1)\cdots \exists x_1(M-1)\cdots\exists x_n(M-1)\\
&\exists u_1(M-1)\cdots\exists u_n(M-1)~~\bigwedge_{i=1}^{n}(f_i(x(0),u(0))\leftrightarrow x_i(1))\wedge
\bigwedge_{i=1}^{n}(f_i(x(1),u(1))\leftrightarrow x_i(2))\wedge
\cdots\wedge \\
&\bigwedge_{i=1}^{n}(f_i(x(M-1),u(M-1))\leftrightarrow x_i(M)).\\
\end{split}
\end{equation*}
According to such expression, I can prove the upper bound of the problem. But I have no idea about how to prove it is $\Pi_2^p$-hard.