texts: Minimum vertices to cover other vertices with max weight

texts:
I have a problem where I'm given the input of a graph. The output would be a set of vertices such that I have the minimum number of vertices to cover other vertices and if there is more than one option then then I'd have to choose the maximum weighted vertex set. I'm trying to approach this in a Dynamic programming though I've always come at a dead end. I'm trying to maximize the number of vertices weights yet at the same time Im trying to minimize the number of vertices selected.

In this case the potential answers can be

{A,B} = 10

{A,C} = 9

{C,D} = 9

{D,B} = 10

Since {D,B} and {A,B} have equal weights then either is a correct solution.

I'm pretty confident that I should be memorizing the weights sum though everything else I've tried led to a dead end. Can anyone provide insights?

This is not a vertex cover problem.

To be honest Im not really sure what my recurrence relation is. I tried thinking about  the problem in such a way that I already have a an optimal solution of a graph G and I want to add more more vertex. The problem is I can add another vertex that may have a lower weight than what the G has in optimal solution, but this new vertex covers all other vertices so I'd have to choose it anyway. The "maximization" constraint fails with respect to previous input as I'm now tackling the other constraint on the problem.


texts: Non-erasing Turing machines and loss of generality

texts:
A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank.  I'm trying to understand whether there is loss of generality because of this restriction.

My guess is that there is no loss of generality, because the restriction above merely restricts replacing characters with blanks, but we can just as easily replace them with some other symbol and construct any rules that might have used blanks to use the new symbol.  I think that's too simple a solution though.

Can anyone give me any insight as to how to show whether or not generality is lost in the special case of non-erasing Turing machines?


texts: What are definite languages? How do you formally define them?

texts:
I have a question in my homework that deals with the concept of a definite language. The question defines a definite language as follows -

"A language L is definite if there is some k(> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w." I'm supposed to do the following -

a) Rewrite this definition formally

b) Prove that every definite language is accepted by a finite automaton

c) Give an example of two definite languages L1 and L2 such that L1.L2 is not definite.

I'm breaking my head over the definition given in the question. In-depth google searches lead me to a few google books and this is what I came across -

Theory of Automata, Arto Salomaa :

Definite languages are completely characterized by the final subwords of a given length k of a string. The behaviour of definite automata depends exclusively on the latest k input letters for some k. Thus, the behaviour is independent of inputs which have occurred at sufficiently remote past moments.

Role of Theory in Computer Science: (edited by Konstantinidis Stavros, Moreira Nelma, Reis Rogerio)

Whether or not a word belongs to a given definite language can be determined by inspecting the last k symbols, where k is a constant only depending on the language. In particular, two words whose length exceed k having the same suffix either both belong to the language or both do not.

More precisely, a language L ⊆ Σ* is said to be definite if and only if
L = E ∪ Σ*Η, for some finite languages E,H ⊆ Σ*.

Theory of Formal Languages with Applications by Dan Simocivi, Richard L Tenney:

Τhis alternative definition was given by Perles, Rabin and Shamir.

A language L over the alphabet A is weakly k-definite if x ε L holds for a word x with |x| ≥ k if and only if the suffix of length k of x belongs to the language L.

For k ε Ν and k ≥ 1, a language L is k-definite if L is weakly k-definite, but it is not (k-1)-definite. A language is definite if it is k-definite for some k ε Ν.

Even after reading all this, I am not able to understand anything regarding the concept of a definite language. How can you precisely define a language to be definite when you don't know what the dependency on the last k symbols of ω is? Shouldn't the definition "depends on the last k symbols" be more clear? What can you quantify as a dependency on the last k symbols, to decide whether ω will belong to L? It doesn't make sense to me. Could you help me in getting a better, clearer, simpler understanding of this? Could you please give some examples, while explaining the concept?


texts: $\sqrt{n} = \Omega(3^{\log{}n})$ is not true? Why?

texts:
Had this question on an algorithm exam. Can any one explain why
$\sqrt{n} = \Omega(3^{\log n})$
is false?


texts:
Let U be a pre-determined and fixed universal set (and |U| = n = 2k for some integer k, so the set may be huge).

I create many arbitrary subsets of U in running time (These sets may be or may not be sparse).

I do not need to check whether an element is in a set.

But I need to be able to

check whether a set is empty,
do the basic set operations difference and intersection, and
calculate the cardinality of a set.

What is the most time-efficient data structure for this? It should be also space-efficient, if possible.

I have bit vector in my mind. Elements of U are numbered from 0 to n-1. Each of n bits represents the existence of the corresponding element.

For k ≤ 5 or k ≤ 6 (depends on the computer architecture and the programming language) I can implement these sets as [unsigned] integers.
But there will be a need for multi-word arithmetics in general case. So I believe, the space complexity of any set is ϴ(n) and time complexities of operations are ϴ(n) using bitwise operations and hamming weight.


texts:
On the Wikipedia page for the Pumping Lemma for Context-Free Languages, a language,
$$
\{b^j c^k d^l | j, k, l \in N\} \cup \{a^i b^j c^k d^l | i > 0, j = k = l\}
$$
is introduced. The pumping lemma proof for this supposedly fails because, given a string without a's, you can pump the b's and, given a string with a's, you can pump the a's.  In either case, all of the possible cuttings are pumpable according to the constraints of the language.

For example, given the string
$$
a^k b^k c^k d^k
$$
you can split vwx over |a| and pump, leaving |b| = |c| = |d|.

Why can the string
$$
a b^k c^k d^k
$$
not be used?

This seems to meet all the constraints of the pumping lemma, and you cannot split vwx across |a|.  If v = a then x must contain at least one b.  The string cannot be pumped for any i > 2 as the |b| will exceed the length of |c| and |b| will exceed the length of |d|.

Is there some reason that |a| > 1 or |a| = k?


texts:
Having a hard time formulating the proof for this. The professor kinda breezed through the problems and I just want an explanation on how best to tackle this and how one would prove what it's desiring:

"Consider the following heuristic for building an approximate TSP cycle for a graph that satisfies the triangle inequality. Begin with an arbitrary node. At each step, choose the vertex u which is not in the current cycle, but has the smallest distance to any vertex in the current cycle. Add u to the cycle and repeat until all the nodes are in the cycle. Prove that this heuristic outputs a tour with a cost which is not more than twice the cost of an optimal tour."


texts: Estimating probability from generative model

texts:
Assume that we have access to a generative model $G$, that takes as input a state-action pair $(s,a)$ and outputs a sample consisting of a successor state-observation pair $(s',o)$, that is, $(s',o)\sim G(s,a)$.

It can be assumed that the states, actions, and observations all take on a finite number of values (can be positive integers).

Is it possible to use the generative model to estimate the probability $P(o|s,s',a)$?

My thoughts:

Fix $s_0,a_0,s_0'$.

  Generate $(s',o)\sim G(s_0,a_0)$
  If $s'=s_0'$, add a particle to bin $b(o)$
  Return to step 1

Continue the above three steps for $M$ runs so that we have $M$ particles in different bins (each bin corresponding to an observation we have seen so far). Now how do we convert the set of particles to probabilities?


texts: Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

texts: If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?


texts: What are the hardest problems that are in P if and only if P=NP?

texts:
I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are proved (/believed/maybe) to be harder than NP-Complete if $P\neq NP$, but are certainly in P if $P=NP$.

I was thinking of the sequence

$x_0 = P$

$x_{n+1} = $"All problems that have a checking algorithm in $x_n$"

e.g. $x_1 = NP$

If $P=NP$, then $x_n = P$ for all $n$. But if $P\neq NP$ is then $x_{n+1}$ different from $x_n$ for all $n$? Is this an ever continuing sequence so that there is no "hardest problem that meets the criteria" (because there would always be a harder one), or does this also hold for $x_\infty$ and would that be the hardest problem that meets the criteria? Or are there even harder such problems?


texts: Any significance to why a lot of big names in AI have math PhD?

texts:
I've been looking into AI research and I've noticed a nontrivial amount of individuals either received a PhD in math or had advisors who received a PhD in math. Some names include (Ben Goertzel, Marvin Minsky, Jürgen Schmidhuber).

I can see how a formal (arguably more difficult) training in math would help tackle issues in AI, but it'd make more sense to do a PhD in AI if one wants to make a career studying AI, no?

In contrast, all the high impact papers for top machine learning conferences (KDD, ICML, NIPS) were mostly from CS labs, but I cannot say that this is the norm in other AI subareas.

Is it actually better to do a PhD in math and do research in a topic that converge with AI?


texts: Do compilers of high programming languages always compile them directly to machine code?

texts:
As an amateur Bash/JavaScript scripter who never wrote one sentence in Assembly, I ask:

Do compilers of high programming languages always compile them directly to machine code, or are there cases when a compiler of some high programming language compiles it to assembly (and then assembler will assemble input to machine code output)?


texts: Perfect Hash Function: How does it cope with lookups outside the set of keys?

texts: I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the perfect hash was generated from.


texts: What's an "applicable event" in the context of the FLP paper?

texts:
I am reading Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382, available here, the paper in which the well known FLP Theorem was proved.

I am having trouble understanding the notion of an "applicable event" used in this paper. Here's a quote from the paper (Section 2):

  Since processes are deterministic, the step is completely determined by the pair $e = (p,m)$, which we call an event. (This "event" should be thought of as the receipt of $m$ by $p$.) $e(C)$ denotes the resulting configuration, and we say that $e$ can be applied to $C$.

I can't understand this definition. When is an event applicable? When is it not applicable?


texts:
I am currently working on a project that involves taking a single color frame, performing image segmentation and then visualization of the scene.

I am currently at the stage of performing alignment between two objects - one in my database and one segmented from picture.

Picture data is processed: for each pixel in the color frame, I have depth data, so from a color frame I am capable of generating a (x,y,z) point for each pixel. Therefore, given my segmentation I am capable of generating a Point Cloud for each object.

So given model in my database and a point cloud ( which might not represent full object - example: I might just see a corner of a table, but I still need to align full table model), I  would like to align object in my database with points in the cloud.

I have done some research and it seems that the method widely used is the Iterative Closest Point (ICP) algorithm. But I have also a different idea, and I would appreciate your evaluation, as I have some concerns regarding ICP.

METHOD 1:ICP

Given that my model and point cloud might not be aligned by default, I have decided to pick points that should be aligned in the result output (assigning corresponding points). So I pick for instance 4 points that should be aligned. However, the issue is obviously that my selection will not be precise and therefore two points sets do not differ just by rotation and translation, but also by small point misalignment.

I want to simplify calculations as much as possible to achieve some kind of convergence.

So I was wondering whether someone has any ideas on how to solve it, and whether you can actually use ICP given this misalignment..

METHOD 2: NON-ICP

Not use ICP, but rather use a simple one iteration calculation. Calculate centroid of selected points and pick one point from model and a corresponding point from the point cloud (obviously this is approximation, because I can't pick exact point), and create two vectors :
"model centroid-to-point" vector and "point cloud centroid-to-point".

Then I could just calculate rotation and translation between these two vectors.

QUESTIONS:

1) Is there a way of solving the ICP issue?

2) Which method seems to be more sensible in terms of accuracy and possible errors?


texts: In "The Complexity Theory Companion" Hemaspaandra and Ogihara define an oblivious oracle TM as an oracle TM where the queries are dependent on the input and not on the oracle. They then show how to turn an oracle $\mathbf{NL}$ machine into an oblivious one. I wanted to know whether this construction will work for other machines as well? So not only for $\mathbf{NL}$ machines.


texts: K Nearest Neighbor using K-D Tree (What ratio makes K-D beneficial)?

texts:
I'm trying to implement a KNearestNeighbor model and came across the fact that many professional models use a K-D tree to index the K Nearest Neigbors. I also read that high-dimensional data makes a K-D tree less useful because you don't eliminate as many vectors for every branch in the tree when traversing it. All of that makes sense, but my question is at what ratio is there any benefit made of using a K-D tree?
For instance, I have a training set of shape (50000, 3072) but I am feeding only 10000 points to the model so the shape the model gets is (10000, 3072)... anyways, I assume these are the only two numbers which are relevant for the model to determine if a K-D would benefit it's runtime.
So in my fit method, I am making an if statement to either make a K-D model or not to make a K-D model for indexing, but I'm not sure what the condition should be. Given
n_data, n_dim = x.shape

I imagine the condition could be
if n_data / n_dim >= 1:
    pass

This is where my knowledge stops. I would be grateful if someone could propose a condition, and educate me about what makes a good condition.


texts: When to use SAT vs Constraint Satisfaction?

texts:
If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it.  Another standard approach is to express it as a constraint satisfaction problem, and try using a CSP solver.  The two feel somehow vaguely similar in what sorts of problems can be naturally expressed in their input format.

Are there any guidelines or rules of thumb for how to recognize, for a given problem, which approach is more likely to yield good results?  Is there any guidance anyone can offer about which sorts of problems can be handled better by SAT solvers than by CSP solvers, or vice versa?

(Obviously, there are some easy problems that can be solved by both approaches.  There are also some hard problems that can't be usefully solved by either approach.  Let's set those aside.  The case where guidance is most helpful are problems where either SAT solvers perform better than CSP solvers, or where CSP solvers perform better than SAT solvers.  How do I recognize when a SAT solver is likely to be a better fit than a CSP solver, or when a CSP solver is likely to be a better fit than a SAT solver -- i.e., which approach to try first?)


texts: research on OR and AND compression in SAT formulas

texts:
this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far.

  A simple proof that AND-compression of NP-complete problems is hard (Dell)

can follow it generally, but not in detail. so:

  how would this theory be described to undergraduates if possible?

looking for sketches, overview and/or some examples and intuition on this line of research from expert(s) of the kind that might appear in an undergrad textbook. also does it have any implication on P=?NP?


texts:
In the introduction of Distance-Sensitive Bloom Filters the authors state:

  The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can be used as a measure of the similarity of the underlying sets.

This statement is followed by a reference to another paper, which could not clarify this statement for me.

Question: What is the precise relation between the hamming distance of two bloom filters and the similarity of the corresponding sets?


texts: Interpretation of '1/3' in IEEE floating point representation

texts:
For a rational number 1/3 below is the floating point representation(64 bit) of decimal expansion 0.3333333....

As per the above bit structure, I would like to interpret the value of exponent(11 bits) and value of fraction(52 bits).

exponent has
 11 bits. How do I interpret exponent value?

fraction has  52 bits.
   Here 0101 is decimal 5. Am not sure if we captured fractional part 33333333... of decimal expansion? To capture fractional part am I suppose to expect 0011 pattern instead of 0101. How do I interpret fractional part?


texts: How does a TLB lookup compare all keys simultaneously?

texts:
I am reading OS Concepts dinosaur book which says, "Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously."

I checked How does a TLB and data cache work? but it does not say anything about the implementation that allows this parallel checking of the keys.

I read something about a parallel hash table here:  http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture27.pdf

Is this the basic idea?  The insertion of a key outputs a frame number and this could either be a hit or miss?


texts: 3-cycle cover decision problem for directed graphs: best known algorithm and maximum size of tractable problems

texts:
I know that the 3-cycle cover decision problem for directed graphs (3-DCC), defined as finding whether a directed graph has a disjoint vertex cycle cover in which every cycle has at least 3 edges, is NP-complete.
Does anyone know what is the actual scaling of the best known algorithm to solve that problem? And, most importantly, what graphs can be tackled with that algorithm?
e.g., I have a graph with 2000 vertices and 2500 edges. Is this solvable? Do I need a supercomputer? What are the limits?


texts: Solve the recurrence relation T(n)=3T(√n)+lg(n)

texts:
Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem.
So, how I will find Θ of T(n)?


texts: kNN: how to improve Spam classification?

texts:
Currently I'm trying to classify spam emails with kNN classification. Dataset is represented in the bag-of-words notation and it contains approx. 10000 observations with approx. 900 features. Matlab is the tool I use to process the data.

Within the last days I played with several machine learning approaches: SVM, Bayes and kNN. In my point of view, kNN's performance beats SVM and Bayes when it comes to minimize the false positive rate. Checking with 10-fold Cross-Validation I obtain a false positive rate of 0.0025 using k=9 and Manhattan-Distance. Hamming distance performs in the same region.

To further improve my FPR I tried to preprocess my data with PCA, but that blow away my FPR as a value of 0.08 is not acceptable.

Do you have any idea how to tune the dataset to get a better FPR?

PS: Yes, this is a task I have to do in order to pass a machine learning course.


texts: balanced partitioning of nonconvex area between multiple agents in a grid world

texts: In the original art gallery problem, there is a non-convex area provided and one has to divide it into regions based on infinite visibility of guards. We assume an unlimited number of guards. However, suppose we only have n number of guards with limited visibility. Then how to divide the area in a balanced way meaning each guard gets roughly same size of area to guard. What kind of algos have been developed in this area till now?


texts:
This is the problem I have:

  Compute the Hamming code with odd parity for the memory word 1101 1001
  0001 1011 (2 pts.). In your solution, mark the parity bits as in the
  following example, where parity bits are: 3, 5, 11, and 13

0001 0100 1011 1100 1001 1
  P  P      P  P

  Note: This is only an example on how you should mark the parity bits.
  It is not a correct code word by any means.

There are 2 things I do not understand:

A 16-bit memory word needs 5 check bits from this formula $2^k -1 \ge m + r$,
where m is the number of data bits and r the number of check bits. But in the exercise we have just 4 check positions.
The check positions usually occupy the positions that are power of 2, for example $2^0$, $2^1$, $2^2$... So why are they asking to use other positions for the check bits?


texts: Why doesn't a time cutoff convert NP problems into co-NP?

texts:
Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations.

You make a tweak to the verifier program, so that if it takes more than $f(n)$ operations, it unconditionally rejects. Then you place it into an NP machine and run it on all possible certificates for some instance of the problem where you're not sure if it has a solution. The unconditional reject after $f(n)$ operations ensures the computation terminates within $f(n)$ operations, even when rejecting. So this NP machine can solve the co-NP dual of the NP problem, where you want to reject in polynomial time when there is no solution.

Except that can't be right, because it seems to imply $\mathsf{NP}=\mathsf{coNP}$ and that's not believed to be true. I have an incorrect assumption or inference somewhere. What is it? Why can't I avoid NP's "negatives might run for a long time or even forever" with algorithm-specific time cutoffs?

A concrete example: suppose you have a 3-SAT verifier that takes no more than $42 n^2$ operations to check a solution to an $n$-clause problem (involving up to $3n$ variables). You then make an NP program like "non-deterministically choose a variable assignment, run verifier for up to $42 n^2$ steps, return its result else reject if it didn't finish". So within $42 n^2$ operations we'll have an answer, and flipping it gives the "is there no satisfying assignment" answer. Why is this not an NP algorithm for the co-NP problem of determining if there is no satisfying assignment to a 3-SAT problem?


texts: Prove that there always exists a line bisecting each of two point sets

texts:
A line $\ell$ for a set $S$ of points is bisecting if the open halfspaces on either side of $\ell$ contain at most $\frac{|S|}{2}$ points.

Now given point sets $A$ and $B$ in the plane, prove that we can always find a line $\ell$ such that $\ell$ bisects both $A$ and $B$ simultaneously. We can assume that no three points in $A \cup B$ lie on a line and no two points share an x-coordinate.

Note that I am not asking for an algorithm separating $A$ and $B$.

So far I have proven the following claim:

  Let $S$ be a point set in the plane containing an even number of points. Prove that, for any point $s \in S$, a bisecting line $\ell$ for $S \setminus \{s\}$ also bisects $S$.

From this claim we can also infer that all separting lines for a point set $P$ with an odd number of points must pass through at least one point $p \in P$. However I am stuck on how to continue. Intuition suggests that one of the lines between points $a \in A$ and $b \in B$ must be simultaneously bisecting (if either of $A$ or $B$ contain an even number of points we can just remove one at random by the above claim). However I cannot seem to prove this is always the case.

Can you give me a hint for the next step?


texts:
I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A_1}$ and $\mathcal{A_2}$ and want to show that the problem $L(\mathcal{A_1}) \not \subseteq L(\mathcal{A_2})$ is in NP by specifying a polynomial proof system.

We defined a polynomial proof system in the following way:

For $L \subseteq \Sigma^*$ the relation $R \subseteq \Sigma^* \times \Gamma^*$ is a proof system for $L$ if $(w,b) \in R \Rightarrow w \in L$ and $w \in L \Rightarrow \exists b \in \Gamma^*: (w,b) \in R$. $R$ is polynomial if there is a polynomial $p$ with $|b| \le p(|w|)$ for all $(w,b) \in R$ and $R \in P$.

Unfortunately I have no idea how to get the relation and any help would be appreciated.


texts:
I need to recover a data block from a repeated stream of data. I'm looking to see what algorithms may already exist for this as it does not feel like a novel situation.

Here are the specifics:

There is an N-length block of data contained in a stream
The block is repeated many times in the stream
the data is highly corrupted, some bytes could just be wrong, where as others can be detected as missing (erasures)
There is a function F(data) which can say if a block represents valid data (the probability of a false positive is virtually zero)
F can also provide a probability value that even if the block is not valid data whether the block itself is valid (but just has too much corruption to be recovered)
The chance of corrupted data is very low compared to missing data

For example, say I have this data stream and wish to recover the 10 length sequence 1234567890. The data is just a rough visual example (I can't guarantee recovery is actually possible from this bit). A . represents a missing byte, and <break> indicates an unknown block of data (no data  and not length known). Note also the Qs as an example of corrupt data.

23.5678901.3456789<break>2345678..1..4567QQ012345678..3456

How can I take such a stream of data and recovery probably blocks of N data? As the actual data includes forward error recovery the block recovery need not be perfect. All it needs to do is give probable reconstructed blocks of data and the F function will attempt to do error recovery.  Thus I expect F fill have to be called several times.

I'd like to find something better than simply calling F at each point in the stream since the error rate could be high enough that no single run block of N can be recovered -- the repetitions in the stream must be used somehow.


texts:
I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S[1] (17) into its appropriate position.

Example: [17, -10, 7, 19, 21, 23, -13, 31, 59].

^# = pivot
^ pointer

My understanding:

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                               ^

Comparison 1. No swap.

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                           ^

Comparison 2. No swap.

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                      ^

Comparison 3. Swap.

-13, -10, 7, 19, 21, 23, 17, 31, 59
                     ^   ^#

Comparison 4. Swap.

-13, -10, 7, 19, 21, 17, 23, 31, 59
                 ^   ^#

Comparison 5. Swap.

-13, -10, 7, 19, 17, 21, 23, 31, 59
             ^   ^#

Comparison 6. Swap.

-13, -10, 7, 17, 19, 21, 23, 31, 59
          ^  ^#

Comparison 7. No swap.

 -13, -10, 7, 17, 19, 21, 23, 31, 59
       ^      ^#

Comparison 9. No swap.

-13, -10, 7, 17, 19, 21, 23, 31, 59
  ^          ^#

Comparison 10. No swap.

Is this how it works? Would it take 10 comparisons and 4 swaps to move pivot S[1] (17) into the correct position?


texts: How does the union of two machines which accept language of form $0^{mx+b}$ look like

texts:
I am doing Shai Simonson's course on Theory of computation. I am not able to understand part b of one of its problem sets.

a. Prove that languages of form $0^{mx+b}$, where m and b are positive integer constants and x ranges from 0 to infinite, is regular.

b. Give an example of a regular set over the alphabet {0} which is not of form $0^{mx+b}$.

In the solution set, for part b, it is given that union of machines which accept language of form $0^{mx+b}$ describes a regular set, but is not of form $0^{mx+b}$.
Q1. I want to understand of what form the union is?
Q2.And also, we are talking about union of finite number of machines, right? Because the union of all such machines(which is infinite) will not be regular. Am I correct?
Q3. I would also like to know is there any other example of a regular language which is not of the given form but is regular.
Q4. I also want to clarify what does set of the union of two such machines will look like. Will it be {$0^{2x_1+3}$ $\bigcup$ $0^{7x_2+4}$}   or
{$0^{2x+3}$ $\bigcup$ $0^{7x+4}$} i.e. will the $x's$ be different or same in both the machines. I think the two sets are independent so they should be different but still want to confirm.


texts: How to store topic-to-topic relationships efficiently and accurately with two huge tables?

texts:
I am scanning Wikipedia's DB and retrieving topics (page names, mostly) and their relationships. I want to use it later to create a visual map.

A topic table stores the id and the label of each topic. A relationship table has an id, a weight, and the two ids of both topics it references. There are usually two rows in the relationship table for each topic pair (dog is more related to the wolf than the wolf is to the dog, for example.)

Now, each topic has a series of several (sometimes dozens) of other close topics (synonyms with a high weight, related terms with a lower but still high weight, etc.)

For example, Caffeine is a topic, and Theanine would be very closely related to it. Same for Coffee beans.

So Caffeine is a common parent but Theanine and Coffee beans aren't aware of their relatedness. The relatedness means that the both topics have a common ancestor (parent topic).

How can I store these various topics and their relations in order to accurately and efficiently (within 1s) get n-topics and compute their relatedness?

My thoughts are:
- Store additional pairs of rows in the relationship table for each cousin and brother topics?
- Or, use the application code (Python, PHP, whatever) to deduce that relatedness by climbing the tree?


texts: Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula

texts:
I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption of what I should do, I would be appreciate if someone can guide me.

First a boolean formula is satisfiable if it can be made TRUE by assigning appropriate logical values, so "deciding the satisfiability" means to decide whether this boolean formula can be made a TRUE result.

Then for conjunctive normal form is means a conjunctive of clauses which are disjunctive inside. and 1-conjunctive normal form means each clause contains one variable, such like A\wedge B.

Now is the problem, what means an algorithm to decide it? I mean isn't the way to decide the satifiability of a boolean formula is try ture and false assiagnments to find whether it can be TRUE as a result? For example: since it is conjunctive normal form so each result of clauses needs to be TRUE, and it is 1-conjunctive normal form, so each variables need to be TRUE. Is this one an accpaptable algorithm to deal with the question?


texts: Which is easier for human perception: type of variable before or after its name?

texts:
In some programming languages type of variable goes before it's name.
In another - name goes first and then type.
Which version loads brain less and allow easier think about problem ?


texts: How to write a coterminating, effectful program?

texts:
[Using Idris for code examples and terminology, but the question is not about Idris per se]

In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in operating systems and interactive applications" is to be modeled mathematically using codata, and that these sorts of programs can even written in a total functional programming language if they found to coterminate. Though I don't yet understand this to the depth in which he lays it out, the idea makes sense, and I'm familiar with the fact that Idris' totality checker (for example) considers cotermination. Thus, we might write the Unix yes program thus:

yes : Stream String
yes = "yes" :: yes

—except that this is not Unix yes, but intra-Idris yes. I cannot run this program and have it do what yes does: I need an effectful program. Stream is a Functor; it seems I want a main : Stream (IO ()).  Let me make the example slightly more compelling by making this an interactive program, as @sigfpe speaks of:

stopOrPrint : String -> IO ()
stopOrPrint s = do
  maybeQ <- getChar
  if maybeQ == 'q'
  then pure ()
  else putStrLn s

main : Stream (IO ())
main = map stopOrPrint yes

But Idris does not accept programs whose main function has type Stream (IO ()). No problem, maybe if I used traverse_ : Foldable t => Applicative f => (a -> f b) -> t a -> f () instead of map, I could get a main with the right type, IO (). However Stream is not a Foldable, and I'm thinking it's not just because Brady forgot to implement it: how do you guarantee that you can fold a potentially infinite value into a finite value? Isn't that kind of crossing over from infinitude to finitude the opposite of totality?

So I'm stuck. I love the idea that with codata and cotermination, we could write a total operating system or even server. But when I actually go to write a socket server in Idris, I end up marking stuff partial; yet Idris' totality checker respects these ideas.

Am I running into a limitation of Idris (or any languages currently in existence), or a more fundamental limitation? If Idris just learned to take a Stream (IO ()) for its main, would that solve it? I have a feeling that still doesn't address the underlying issue, because now you have a bunch of disconnected IOs: don't you actually want an infinite IO monad (can there be such a thing?)?

Is it possible to mix cotermination and effects, in a pure, total functional language? Has it been done? If not, what would it have to look like?


texts: Something I don't understand about Genetic Algorithms

texts: I've had a bit of experience programming Neural networks but I am fairly new with genetic algorithms (I'm only 17). I have a major issue that I can't understand. If a child get's one chromatid from one parent and another from another parent, then the genes are crossed over, how do you determine which alleles are active in the child? How do other people go about mating with genetic algorithms. No need to go deep into it because I also want to work somethings out for myself but a general idea would be good enough. Thanks in advance.


texts: Most Efficient Way to Map Generic Input To Generic Output

texts:
Lookup tables are one way to map x values to f(x) values.  This lets you do computation in advance, and can give a low cost (performance wise) answer to complex calculations when they are needed in performance intensive applications.

Another method to map x values to f(x) values is to use the chinese remainder theorem to encode values into a (often large) number and use modulus to get the values back out

For instance, if the modulus "lookup table" was the number 27, it could encode the values 2,1,0 by using divisors 5,2,3 respectively:

$\begin{array}{c|c}
\text{Input (x)} & \text{Math} & \text{Output (f(x))} \\
\hline
0 & 27 \% 5 & 2 \\
1 & 27 \% 2 & 1 \\
2 & 27 \% 3 & 0 \\
\end{array}
$

(More info on that technique here: http://blog.demofox.org/2015/11/13/hiding-a-lookup-table-in-a-modulus-operation/)

The modulus method seems like it would always be slower and take more memory than a straight lookup table.

Is there a more efficient mapping of input values to output values than just using a table?

I'm interested mainly in efficiency of computation time to pull a result out of a mapping, but memory efficiency is also interesting, as well as efficiency in creating the object to begin with, if anyone has any interesting info on that.

Thanks!


texts:
I am new to this forum and this is my first post. I am interested in solving a problem, but cannot find the way to think about it. If anyone can guide me through it, I would be obliged:

Let F be some system of axioms. You can assume F is sound (that is, it only proves true statements), and also that F is strong enough for Godel's Incompleteness Theorem to apply to it. Let G ( F ) be the mathematical encoding of "This sentence is not provable in F ." Also, let MF be a Turing machine that generates all possible F -proofs, one by one, and that halts if and only if it encounters a proof of G ( F ).

a) Does MF halt? Why or why not?

b) Is there a proof in F that MF halts, or a proof in F that MF does not halt? Why or why not?


texts: Prove that the next multiple of 4 is obtained using the next formula

texts:
I was reading an assembly procedure that needed to align addresses on 4 bytes boundary for performance reasons so it has used the next statement that i formulated as a theorem to be proven.

Let $s$ be an integer that is not a multiple of 4 ($s \% 4 \neq 0$). $m$, the first next multiple of 4 such that $m \gt s$ is obtained using the following formula, where the operands are expressed in base 2 (Binary): $m = s + (\lnot s \land 11)$ ($\lnot a$ will return the 2's complement of $a$).

How to prove that ?


texts: What's the difference between $a^*+b^*$ and $(a+b)^*$?

texts: What's the difference between the regular expressions $a^*+b^*$ and $(a+b)^*$. Do both of these generate the same language? I was told in a lecture that $(a+b)^*$ will generate string concatenation of $a$ and $b$. How could this be possible?


texts: What combination of data structures efficiently stores discrete Bayesian networks?

texts:
I understand the theory behind Bayesian networks, and am wondering what it takes to build one in practice. Let's say for this example, that I have a Bayesian (directed) network of 100 discrete random variables; each variable can take one of up to 10 values.

Do I store all the nodes in a DAG, and for each node store its Conditional Probability Table (CPT)? Are there other data structures I should make use of to ensure efficient computation of values when some CPTs change (apart from those used by a DAG)?


texts: Irregularity of $\{a^iba^j : i \neq j\}$ using pumping lemma

texts:
Proving the language $L=\{ a^i b a^j |\ i<j,\text{ or }i>j;\ i,j>0 \} $ is not regular, I am trying to use the pumping lemma for regular languages:

pumping length $:= m$

case 1: $i<j; j=m$

$w_1 = a^i b a^m = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

$a$s only
$a$s + $b$
just $b$

However, this leads to $xy^hz\ \not \in L\ \forall h,\ h>0$.

case 2: $i>j; i=m$

$w_2 = a^m b a^j = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

$a$s only

Pumping with this $y$:
 $xy^hz\ \in L\ \forall h$ holds true.

As this answer does not seem to even consider the second case, is the first case sufficient to proof the language is not regular?
However, taking a look at this answer I think I'd have to considere the second case as well, in order to cover all possible $xyz$ combinations.


texts: Time Complexity: Show the following problem belongs to FP

texts:
Let $n > 0$ be an integer. Show that the rounded square root function
$f(n) = ⌊\sqrt n⌋$ belongs to FP.

Suppose $n=x+y$, where $x$ is the largest perfect square which is at most $n$, and $y$ is the remaining integer. For a given $x$, checking whether $x$ is a perfect square is in time $O(\log n)$ (using binary search). Also, the remaining square root of $y$ part can be rounded off to 0 or 1 accordingly, which is in constant time $O(1)$. Is this rounding computation in constant time?


texts: Shortest continuous path between shapes without passing thru other shapes, in a specific order?

texts:
I have the following points, shapes, and paths.  I would like to find a path that goes through all of them:

I want a path that first traverses the circle, then traverses the square, then traverses the star in the middle, in that order.

It's simple to go to the circle from the bottom left and around it, hitting each point.  However, the second shape (the square) is in the top right corner, so I have to go around the star (so I don't cross it) and traverse the square. Finally, I go to the middle, hit each of the points of the star and done. Once that is done, going backwards is pretty easy.

This is an easy example.  In my situation, though, there can be hundreds of shapes in between each of them and I have to go to each shape in the order they are stated.

How do I calculate a path that avoids a particular shape (e.g., the star)? I'm not sure what algorithm to look for. Is it a Travelling salesman problem? A*?

The shapes are defined on a grid. This is what I mean:

"1" means the path must go thru here and "0" is empty space which can be used to get to from one place to another.


texts: I am working in image segmentation with super pixels. My data is a large matrix describing various attributes of each stick of pixels (such as height, width and disparity). The data comes from an image taken with a stereo camera so for each stixel I can get a respective point in 3D. From these points I have built a graph where each vertex is the stixel ID, the edges represent proximity (if a stixel is a neighbour of another) and the weights are the euclidean distance. Since I must cluster by orientation planes I thought that the branches of an MST would give me an initial set of orientation planes and starting clusters. However, I don't know how to cluster the MST's branches using the weights. I also tried graph clustering with MCL in the full graph but the results where not very good. Is there any algorithm that could cluster a tree's branches?


texts: Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

texts:
I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness.

This can be regarded as a reference request post. Any links are appreciated.

At least, this can be helpful in drastically mitigating the frequently asked questions related to homework assignments that are giving so much credit to @David Richerby, @D.W., @Yuval Filmus.


texts: Algorithm that hashes a collection of sets following their disjointness relation

texts:
I wonder whether there is a simple algorithm to do this work:

Say I have a collection of objects $C$, and a binary relation $R: C\times C$ that is auto-reflective ($\forall c\in C: c R c$)   , and symmetric ($\forall b,c\in C: b R c \implies c R b$). The relation is not necessarily transitive.

I want to find an integer function $$h: C\rightarrow \text{Integer}$$ so that
$$\forall b,c\in C:   h(b)\neq h(c) \implies R(b,c) $$

Example:
Let $$C=\{1,2,3\}$$  $$R=\{(1,1), (2,2), (3,3), (1,2), (1,3), (2,1), (2,3)\}$$
$$h_1 = \{1\rightarrow 5, 2\rightarrow 6, 3\rightarrow 7\}$$
$$h_2 = \{1\rightarrow 5, 2\rightarrow 7, 3\rightarrow 7\}$$
then $h_2$ is a correct answer. $h_1$ is not, because $h_1(2)\neq h(3)$ yet $R(2,3)$ does not hold.

More concretely, my question comes from the following real concern: I have a collection of sets $C$, between some of them being disjoint. I want to find a hash function $h$ that is able to distinguish the sets by their disjointness, so that for any  sets $b,c$ of $C$ belonging to different hash buckets, I can conclude that they are disjoint. This is motivating because the underlined $C$ may have a huge cardinal.


texts: Could an OS relinquish control back to the bootloader?

texts:
I'm wondering if it is feasible for an OS to return control back to the bootloader, and boot a second OS after itself.

Reason being -- I've been musing on bootkits, and wondering if it would be possible for a bootloader to run a micro-linux distribution hidden at the end of the drive (that charades as a slowly booting Windows install) that, after running its payload, returns control back to Windows boot.

From the point of view of the user, it would just be a very slow boot. It could even be made to look like it's just Windows going through a pre-boot update process.

As far as I can tell, this would just require the hidden malicious OS to be able to pass control back to a bootloader.


texts:
How to prove that the problem VERTEX-COVER belongs to $NP$?
The problem VC is defined as follow:

INSTANCE: Graph $G = (V,E)$ and an integer $k$
PREDICATE: Is there a subset $V_1 \in V $ s.t $\mid V_1 \mid \leq k $ and $\forall (u,v) \in E $ $u \in V_1  $ or $v \in V_1$ ?

My approach:
I know that the class $NP$ can be defined as the class of all problems that can be solved using non-deterministic algorithms that runs in polynomial time.
Therefore, i can guess if $\mid V_1 \mid \leq k$ then test for each node in $E$ if $u$ or $v$ belongs to  $V_1$. In this case return $TRUE$, otherwise $FALSE$.


texts:
Possible Duplicate:
  Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free

Do there exist context-free grammars for the following two languages:

The set of all strings of the form $xx$ where $x$ is a sequence of $0$'s and $1$'s. (For instance $0110101101$.)
The set of all strings of the form $xy$ where $x$ and $y$ are sequences of $0$'s and $1$'s, $x$ and $y$ have the same length and $x\neq y$.


texts:
Finding sum of a geometric progression is simple when we just need to report the sum,
but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.

I have a geometric progression: $$\frac{1}{n} + \frac{n-1}{n^2} + \frac{(n-1)^2}{n^3} + \dots$$

Now the sum will be something like

$$1-\left(\frac{n-1}n\right)^r, $$
 where $r$ is the number of terms.

Now, what if $r$ is large, say $10^4$?

How do I calculate this?

I used modular exponentiation to calculate the powers of $n-1$ and $n$ fast, but as we can see these numbers can be quite large.

Let's say $1-(\frac{n-1}n)^r = P/Q$.

I tried to output $PQ^{-1}\bmod1000000007$ for this, where $Q^{-1}$ is the multiplicative inverse of $Q$ modulo 1000000007 .

I individually found $(n-1)^r$ and $n^r$, and then $P = n^r - (n-1)^r$, and using same modular exponentiation, it's easy to calculate the numerator. But for the denominator, what I am doing is calculating $n^r\bmod1000000007$, and then taking its modular inverse with respect to 1000000007, but I think that's not the correct way to do it.

So how to calculate modular inverse of $Q$ when $Q=n^r \bmod 1000000007$ and $r$ can be large?

I am using Fermat's little theorem, now I just only need advice if it is correct to calculate $n^r$ first using modular exponentiation and then taking its modular inverse, or is there any other way?


texts: What does it mean " The outer level page table need not be page aligned?

texts:
The question is in context to multilevel page table. I was trying to solve numerical on multi-level paging and noticed that page size might not be same at all levels. I came across the point "Outer level page tables need not be page aligned to inner page tables".

Question 1: Does this mean that outer level page tables need not have same page size as inner page tables?

Question 2: If the sizes at different levels of paging are different, then will an outer page table's entry have to contain the exact frame address, i.e., frame number + offset, because page sizes are different across all levels?


texts: Is it possible to find all shortest paths in undirected weighted graph in polynomial time

texts:
I'm trying to practice some theory on graphs:

Namely, we have given connected undirected weighted graph with $N$ nodes and $M$ edges, let's say we want to find the shortest paths between node $1$ and node $N$. But, not only that we want to find all the paths with same shortest distance between $1$ and $N$.

Now I was wondering that if we have given $N = 300$ this number (of shortests paths) can be huge, my question is: is it possible to find all shortest paths in graph with at most 300 nodes in polynomial time.


texts:
I'm reading multi-level cache and came across a question through  which i got confused. I've read that

  Between processor and Cache Word/ Byte is transfered
  Between Cache and Main memory Block(Block of words) is transfered.
  If there is a miss in lower level cache and hit in higher level
  cache, first Block of words is transfered from higher level cache to
  lower level cache and then particular words is transferred to the
  ptocessor from lower level cache.

In case of multi-level caches cache at lower level generally has lower size as compared to cache at higher level. Hence Block size of lower level cache is generally smaller than block size of higher higher cache.

So, How actually Block of words is transferred between caches.

For instance suppose there two caches $L_1$ and $L_2$ with block size 4 words and 16 words respectively, connected with a databus having capacity to transfer 4 words at a time. Now Suppose there is a miss in $L_1$ cache and a hit in $L_2$ cache. Then Do we transfer 16 words or only 4 words from $L_2 \rightarrow L_1$


texts:
Is MDP Considered as The Model-based Value Iteration in/of Reinforcement Learning?
If no, then Reinforcement Learning is all about being Model-free learning. Right?


texts: In case of a given graph , Is that possible to build trapezoidal map in linear time

texts:
[This regarding to Computational geometry in CS]

Let's say that I have a graph G which contains v vectices and e edges, For instance a veronoi diagram VD(G).

I'd like to build a trapezodial map out of my given graph,

Is that possible to build trapezodial map in linear time for a given graph, Instead of O(nlogn) regular construction time ?

I have been thinking about sweep line trapezoidal map construction where for each edge during the sweep line would construct the upper and lower sites.

Thanks in advanced


texts: Induction rules for reflexive, transitive closure

texts:
I'm trying to solve an exercise on inductive definitions, the premiss is:

Let $\to$ be a relation on $A$ and $\to^*$ its reflexive, transitive closure, which is defined by following two rules:

$a \to^*a$ (reflexive)
${a \to^*b \quad b \to c \over a \to^*c }$ (step)

The questions are:

What are the induction rules for $\to^*$?
Show that  $\to^*$ is reflexive.
Show that  $\to^*$ is transitive.

The first question startles me, I view ${a \to^*b \quad b \to c \over a \to^*c }$  as the induction rule. Is this the complete answer?

And can I show the reflexivity with ${a \to^*b \quad b \to a \over a \to^*a }$?


texts:
Is the following problem decidable?

  Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$?

It is given that the following problem is undecidable

  Given a context-free grammar G, is $ L(G) = \Sigma ^*$ ? $\ (1)$

and this problem decidable

  Given a context-free grammar G, is $ L(G) = \emptyset $ ? $\ \ \ (2)$

My thought is this:

$L(G) \subseteq L(R)$ is the same as $ L(G) \cap \overline{L(R)} = \emptyset $. So, since regular languages are closed under complement, and the intersection of a $CFL$ with a $RL$ is a $CFL$, $L(G) \cap \overline{L(R)}$ is a $CFL$. Now, $(2)$ is decidable, so if we can create a context-free grammar for $L(G) \cap \overline{L(R)}$ and give it as input to a decider for $(2)$ we have decided our initial problem.

Is my thought correct? And if yes, how can create such a grammar?


texts:
$T(n) =
\begin{cases}
2: & n=0\\
5: & n=1 \\
2T(n-2) - T(n-1): &n \geq 2
\end{cases}$

I have found a few examples including https://math.stackexchange.com/questions/1316301/if-tn-tn-1-2tn-2
But I am still lost about how to solve this one.


texts: Which complexity classes are $\mathsf{RE}$?

texts:
Given some complexity class $\mathsf{C}$, I want to know if there exists a function (Turing machine) $F:\mathbb{N} \to \mathsf{C}$ such that, if $S$ is any set for which the problem $x \mapsto x \in S$ is in $\mathsf{C}$, then $F(n)$ is a Turing machine which (partially, if $\mathsf C = \mathsf{RE}$) decides $x \in S$ for some $n$.

Note that if $g$ and $h$ are two Turing machines that decide $x \in S$, then $F$ only needs to enumerate one of them (hopefully this makes the problem easier). Thus the title is a bit wrong, but kept as it is for lack of a better one.

Trivially, if $\mathsf{C}$ equals something in the Chomsky hierarchy, such machine $F$ exists (enumerating all grammars of the required type). I'm interested in the less obvious classes.


texts:
I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me it seems trivial.

The method of solving the problem says to convert the original bipartite graph into a network, by creating a Source and Sink vertices, directing all edges towards the Sink and setting all edges' capacity to 1. Then I should run Ford-Fulkerson. Fair enough.

My question is, can't I just do this linearly? (Obviously not, but I don't see why). The goal of the problem seems to be to find a maximum matching in a complete bipartite graph - i.e. the maximum number of edges between the two "sections" of the graph that do not share any vertices.

To illustrate, see this picture

In the first graph the maximum matching will be 2 - any of the two vertices on the right may only be connected to a single vertex on the left. Since the edges are unweighted, it doesn't really matter which?
Similarly in the second graph, the matching will again be just 2.

Can you tell me where am I thinking wrong? I don't understand where the complexity of the problem comes from.

And sorry if any of the terms were used incorrectly, I am not studying CS in English. Thanks


texts: Algorithms to convert 2D videos to 3D ones

texts: Are there published algorithms that can convert 2D videos to 3D ones? If there are few published algorithms for this I am also interested to know how the conversion quality is.


texts: Time complexity for count-change procedure in SICP

texts:
In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem statement suggests drawing the tree for (cc 11 5) - which looks like this):

 ; count change
 (define (count-change amount)
   (define (cc amount kinds-of-coins)
     (cond ((= amount 0) 1)
           ((or (< amount 0) (= kinds-of-coins 0)) 0)
           (else (+ (cc (- amount
                           (first-denomination kinds-of-coins))
                        kinds-of-coins)
                    (cc amount
                        (- kinds-of-coins 1))))))
   (define (first-denomination kinds-of-coins)
     (cond ((= kinds-of-coins 1) 1)
           ((= kinds-of-coins 2) 5)
           ((= kinds-of-coins 3) 10)
           ((= kinds-of-coins 4) 25)
           ((= kinds-of-coins 5) 50)))
   (cc amount 5))

Now... there are sites with solutions to the SICP problems, but I couldn't find any easy to understand proof for the time complexity of the algorithm - there is a mention somewhere that it's polynomial O(n^5)


texts: Complexity Class of an Algorithm with two Inputs

texts: Consider a problem with two inputs like (P,L) and |P|=n and L is some positive integer. If my algorithm had a complexity of O(n^L), would that still be polynomial? Or is it exponential? I'm not sure if I should view L as a constant or as 'size of input', since it's not a size but just some number (as in, Knapsack for example, select items of weight <= L). At the same time, L is part of the input and not fixed.


texts: Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

texts:
We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can be generated just by concatenating $0^9$. Hence we can represent $L^*$ using a FSM.

My Question :

Here I got these numbers $120$–$128$ for $m^2$ by trial and error. Is there any formal method to arrive at these numbers?
If we consider $m^2$ to be a function such that we get $L^*$ is regular, will it also be regular for $m^3$?


texts: Decide if a language has a word of a given size

texts:
Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable:

$$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ such that } |w'| \leq |w| \}$$

I.e., $w \in L'$ if $L$ has some word with length smaller than $|w|$.

The way I was thinking to show that is observing that $L \cap\Sigma^{|w|}$ is finite, and $(L \cap \Sigma) \cup (L \cap \Sigma^2) \cup \ldots\cup (L\cap \Sigma^{|w|})$ is finite too, hence decidable. But the main thing I am struggling with is how can any algorithm for $L'$ know if some $u \in L$? this is undecidable, so it's unclear to me how any algorithm for $L'$ can verify that indeed some word is in $L$


texts: Complexity of space density and sequentiality

texts:
I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms.

When we measure algorithms we tend to give the big-Oh notation such as $O(n)$ and usually we are measuring time complexity. Somewhat less frequently, though still often, we'll also measure the space complexity of an algorithm.

Given current computing systems however the density of memory and the sequence in which it is accessed plays a major role in the practical performance of the algorithm. Indeed there are scenarios where a time complexity algortihm of $O(\log n)$ with disperse random memory access can be slower than a $O(n)$ algorithm with dense sequential memory access. I've not seen these aspects covered in formal theory before; surely it must exist and I'm just ignorant here.

What are the standard metrics, terms, and approaches to this space density and access sequentiality?


texts: How to prove quantum circuit identity in Qiskit?

texts:
I am working on a simple quantum circuit identity. I proved it on paper with the tensor product, but i'm having trouble showing that with qiskit. I know I need to measure them somehow but i don't know how.
Can someone help? :)


texts:
I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know :

A-> B
A-> C
C -> B

A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for B. I know that A belongs to NP, B and C are NP-complete. Moreover I can write an algorithm for A with a quadratic number of calls to C.
can I deduce something about the complexity of A?


texts:
How to prove that this crossword puzzle is NP-complete?

We have an instance of crosswords in a square grid $G$ of size $m \times m$.
We have a set of black boxes $N$.
We have a dictionary of words  $D \subseteq\Sigma^{\ast}$, where $\Sigma$ is a finite alphabet.

The question is whether there is a way to fill in the white boxes ($G\setminus N$) so that all the horizontal and vertical words belong to $D$. Here we suppose $|\Sigma|\geq 3$.

Also note that the reduction should not create a dictionary that is too large.


texts: Is there an efficient algorithm to extract the farthest ends of a thin contour?

texts:
Let's say you have pixel bitmaps that look something like this:

From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the fastest algorithm to pick, from the set of polygon points, the ones that are closest to the natural "endings" of the contour (i.e. the two tips at the end of the U in this case) - so there are $2$ points in the output.
Somehow it looks like it should be related to curvature, although the algorithm should support a large variety of possible shapes, including S, W and other largely curved shapes so I'm hesitant to set any kind of threshold on curvature.
I've tried convex hull methods as well as a couple of variations of the rotating calipers method but still I've found nothing that will convince me that I can reliably and quickly identify the endings/tips of any curved thin line. It's always impressive how humans can pick up on these natural features so fast!


texts: If two vertices point to one another in a directed graph, is the graph then considered cyclic?

texts: Suppose you have a directed graph. Vertices a and b are part of the graph. There is an arrow pointing from a to b and an arrow pointing from b to a. Does this make the directed graph cyclic?


texts:
So I know that scheduling has been covered in other articles, but because my provided values are different and decimals are used, I am having difficulty wrapping my head around it. I have reviewed all of the other posts already but would like clarification on my specific values if possible.

What is the average turnaround time for these processes with the FCFS scheduling algorithm?
What is the average turnaround time for these processes with the nonpreemptive SJF scheduling algorithm?
The SJF algorithm is supposed to improve performance, but notice that we chose to run process $P_1$ at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 2 units and then nonpreemptive SJF scheduling is used. Remember that processes $P_1$ and $P_2$ are waiting during this idle time, so their waiting time may increase.
What is the average turnaround time for these processes with the preemptive SJF scheduling algorithm?

The values (including a make-shift Gantt chart) are as follows:

1. FCFS

\begin{array} {|r|r|}
\hline
P_1 &P_2 &P_3 \\
\hline
0-5 &5-8 &8-9 \\
\hline
\end{array}

Completion times:
$P_1=5, P_2=8,P_3=9$
Turnaround Time = 5.866667

2. Non-PreEmptive SJF

\begin{array} {|r|r|}
\hline
P_1 &P_3 &P_2 \\
\hline
0-5 &5-6 &6-9 \\
\hline
\end{array}

Completion times:
$P_1=5, P_2=9, P_3=6$
Tunaround Time = 5.2

3. Future-Knowledge (Non-PreEmptive SJF with Idle time)

\begin{array} {|r|r|}
\hline
- &P_2 &P_3 &P_1 \\
\hline
0-2 &2-5 &5-6 &6-11 \\
\hline
\end{array}

Completion times:
$P_1=11,P_2=5,P_3=6$
Turnaround Time = 6.2

4. PreEmptive SJF (SRTF)

\begin{array} {|r|r|}
\hline
P_1 &P_2 &P_2 &P_3 &P_1 \\
\hline
0-0.4 &0.4-3 &3-3.4 &3.4-4.4 &4.4-9 \\
\hline
\end{array}

Completion times:
$P_1=9,P_2=4.4,P_3=3.4$
Turnaround Time = 4.133333333

Hopefully these values are correct. If they are not, could you please explain the process so that I can understand how to properly calculate it myself? Thank you in advance for any assistance!


texts:
I have a directed graph. How to find in it some set of cycles that are pairwise
do not intersect, but cover the entire set of vertices, if a cycle from one vertex is not considered a cycle, but cycle of the two vertex is a cycle?


texts: Data structure for finding the sum of edge weights on a path

texts:
Let $T$ be a tree, and there is a weight function on the edges $w:E\to X$. $(X,\oplus)$ is a monoid structure.

Define $f(u,v) = \bigoplus_{i=1}^k w(e_i)$, where $e_1,\ldots,e_k$ is the unique path from $u$ to $v$.

Can we preprocess the tree, such that we can use linear space (or close to linear space), so we can answer queries $f(u,v)$ in $O(\mathrm{polylog} (n))$ monoid operations? The problem become more interesting if we allow removing edges and add edge between two vertices in distinct trees.

We can also ask the question on a DAG, with weights from a commutative monoid. We want to preprocess in linear time, and query the result of $f(u,v)= \sum_{e} w(e)$, where $e$ is in some path from $u$ to $v$, in $O(\mathrm{polylog} (n))$ time.

If we consider the very special case where the entire graph is just a path, then what we want is a dynamic version of a Fenwick tree. A finger tree can solve the problem in $O(\log n)$ time.


texts: Must the champion of an entire tournament beat the champion of a possible tournament among other players?

texts:
I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given competition between two players is known, but the order of competitions is not. Suppose that I have some tournament of the form $p_1, p_2, p_3, ..., p_n$ and I know that $p_1$ may win the entire tournament (depending on the order of competitions). Can I show that $p_1$ must beat some possible winner of a tournament on just $p_2, p_3, ..., p_n$?

I originally came to this while proving the correctness of an algorithm to determine the list of possible winners of a general tournament, but this specific subproblem is giving me trouble.

To begin an attempt at a solution, I offer that in the contrary case, $p_1$ must only compete against and beat some sequence of "losers" (players who cannot win the tournament on just $p_2, ..., p_n$ no matter the order played), with no winners losing to $p_1$. This implies that at some point, a loser must defeat a winner. This may be impossible? I can't prove that, and I don't know whether that's even true.


texts: Path optimization in a DAG: maximizing number of least cost arcs

texts:
I've got the following problem.

I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$.

The optimal path has to maximize the number of least cost arcs.
In the example:

R->B->S is the least cost path but it's not the optimal.
R->-A->D->S costs less than R->A->C->E->S , but the latter is the optimum as it goes through more, least cost arcs.

My current problem, which constitute the object this question, is to find a way of defining formally how to compare two paths according to my intuitive understanding, as comparing them comes before choosing the optimal one.

Of two paths, the better one is the one that traverses the highest number of least cost arcs.

I have been considering three ways, some that seem not fully adequate for my purpose, but would welcome other suggestions.

My three  ideas are the following:

Minimizing the average of the cost of arcs on the path.

Minimizing the average is not fully ok: imagine to have a path with cost [3,12], and a path with cost [3,10,10]. The average of the first path is less than the average of the second, but the second is the optimal as it traverses more paths.
Comparing individually the arcs of the paths

Given two paths $A$ and $B$:

Let $A$ = [$a_1,\ldots,a_n$] and
$B$ = [$b_1,\ldots,b_m$] where $a_i$ and $b_i$ are the arc costs of $A$ and $B$ respectively.

Then $A$ is better than $B$ if $\sum_{i=0}^n card(B < a_i)$ <  $\sum_{i=0}^m card(A < b_i)$ where $card$ represents the cardinality of the set, and $B < a_i$ is defined as $\{b_j  \in B \mid b_j < a_i\}$, the comparison being on the weight of the concerned arcs.

However, with this second approach I get many ties between different paths, increasing the risk of getting a suboptimal path.
Comparing the min-max of the arcs weights for each path.

Another possibility is to compute the min-max of the arcs of each path, and choose the smaller one. It is intrinsically different from the other approaches.

But it is  not fully what I seek to achieve.
For example, min-max over [1,1,1,3] and [2,2,2,2] chooses the latter one, while the best one is the first.

To motivation behind my intuition is the following: each node is a "checkpoint" that the solution may traverse on its way from the node $R$ to node $S$.
The goal is to output a sequence $Q$ with an associated "precision"

if the chosen path is R->A->D->S, then $\;Q\;$ is $\;\;$A $\pm$ 10, D $\pm$ 5, S $\pm$ 7

Clearly, the optimal solution has to be as precise as possible, so the optimal path has to emit the maximum number of least cost arcs.

Once the comparison of paths has been formalized precisely, my problem will be to compute the optimal path on a given graph. But right now the  question is only to find a proper way of comparing paths. The role of the graph structure is only, possibly, to help convey the intuition of my problem.


texts:
In response to a clock interrupt, the OS saves the PC and user stack pointer
of the currently executing process, and transfers control to the kernel clock
interrupt handler.

Then the clock interrupt handler saves the rest of the registers, as well as other machine state, such as the state of the floating point registers, in the process PCB.

Why these information are saved in 2 separate moments ? And what is the purpose of "PC and user stack pointer" ?


texts: Complexity of finding 7th smallest element in a min-heap?

texts:
I don't know if it's allowed to traverse nodes in a min-heap.

Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus giving the complexity of $\Theta(1)$.

But if traversing is not allowed, then for finding $7^{th}$ smallest element, I'll need to call extract_min() 6 times, leading to a complexity of $\Theta(\log n)$, which I think should be correct, but not sure.

My understanding is, if I'm traversing, then it's not a min-heap, it will be an augmented min-heap. Is it correct?


texts: What are some "easy" unreasonable implications of O(1) time memory access?

texts: If you are given a memory address $n$ bits long, then you need to at least process those bits. Hence, if you have $N$ memory available, addressed by $n$ bits, it would take  $O(\mathbf{log}(N)) = O(n)$ time to access a given memory location, at best. I can see why it might be convenient to assume $O(1)$ memory access time because we don't go out of our way to abuse it in day-to-day arguments, and because $\mathbf{log}$ grows slowly. That said, what are some "easy" unreasonable implications of being able to access memory in $O(1)$?


texts: How to represent a double push or double pop operation in push down automata

texts: I want to know the theoretical representation of a double push or a double pop in pda


texts: Checking validity of formulas in first-order logic

texts:
Given four formulas in first order logic. Which of the following formulas are not valid? (In logic a proposition is valid if it never evaluates to $\bot$.)

$(\exists x P(x)\to Q)\to (\forall x (P(x)\to Q))$
$((\neg P\to Q)\wedge(P\to R))\to (\neg P\to R)$
$(\exists x(P(x)\to Q(x)))\leftrightarrow  (\forall x P(x)\to\exists x P(x))$
$(\forall xP(x)\to Q)\to (\forall x (P(x)\to Q))$

According to proof by negation, for example if we negate formula in $1$ then we get $\bot$, as a result this shows that $1$ is valid. Instructor said only $4$ is not valid, but I think both $2$ and $4$ are not valid according to proof by negation.


texts: A "natural" decidable problem not in $\mathsf{NP}$?

texts: Are there any "natural" examples of decidable problems that are definitively known not to be in NP?  The decidable languages I know of that are not contained in NP are usually derived from the time hierarchy theorem, which produces "artificial" languages based on diagonalization.


texts: I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth understanding of probability. What would be a good probability book to learn from that would be intuitive, but also have some mathematical rigor to it?


texts: Searching in sorted array with $O(\log n)$

texts:
Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows:

Suppose array $A[1..n]$ consist of $n$ distinct integers that is
sorted in ascending order, then How many of below problems could be
solved in $O(\log n)$?

and there were three statements;

Find an $i$ index so that $A[i]= i $
Find an $i$ index so that $A \left \lfloor{i}\right \rfloor = 3i +2$
Find an $i$ index so that $A[i]= 4i^{2} + 3i + 5$

The answer sheet stated as one statement is true, Also there was no clue on which statement is true.

What is my issue?
So I think the first and second statements could be true, since the array is sorted then we can use Binary search with $O(\log n)$ to find the element with index $i$, also the first two statements are linear, thus I think that's what the question wants, If it's not then I don't know what the question exactly wants, any explanation would be handful.


texts: Can every state in a DFA be an accepting state?

texts:
I know that we can have 0 accepting states in a DFA, it would just recognize the empty language. What about the case of all states being accepting? Would that mean it would recognize all of the strings in the DFA's particular alphabet?

Thanks


texts:
In a directed graph where the edges may have positive or negative weights, the Bellman-Ford algorithm detects cycles in which the sum of weights is strictly negative ($<0$). I need to detect cycles in which the sum of weights is weakly negative ($\leq 0$). Here is my current idea:

For each edge $e$, replace the weight $w_e$ with a vector of length 2, $(w_e.-1)$.
Run Bellman-Ford on the graph with vector weights, where addition of vectors is done elementwise, the zero element is $(0,0)$, and comparison is done lexicographically.

Each strictly-negative cycle in the new graph has a weight of $(W,k)<(0,0)$, where either $W<0$, or $W=0$ and $k<0$. Since $k<0$ for every cycle, this amounts to $W\leq 0$, so in the original graph it is a weakly-negative cycle.
Conversely, each weakly-negative cycle in the original graph has a weight of $W\leq 0$, so in the new graph it corresponds to a strictly-negative cycle.

Is this algorithm correct? Is the proof sufficiently accurate?


texts: Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

texts:
There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union.

I'm currently interested in a very similar problem, but don't know how to convert one to another:

Given a set system with $n$ sets and a bound $k$. Select as many sets as possible while their union is at most $k$.

Is this problem NP-hard? Any hint is welcome!

Updated 2020: I found a paper called "Unbalanced Graph Cuts" by Hayrapetyan et al. [ESA'05] which describes the Minimum-size bounded-capacity cut (MinSBCC) problem which is very similar to what I looked for.


texts:
I've seen a few questions on this site about Deep Dream, however none of them seem to actually speak as to what DeepDream is doing, specifically. As far as I've gathered, they seem to have changed the objective function, and also changed backpropagation so that instead of updating weights they update the input image.

I'm wondering if anyone knows exactly what Google did. They mention in one of their articles imposing Bayesian priors when they carry out their optimization, and with this I can imagine that getting the neural net to spit out an image for each label is not that difficult - we can simply set the label, and then optimize the input vector accordingly.

However, the interesting part of deep dream is that it does this per layer, and in this regard I'm not quite sure how it emphasizes the details  in a per layer way.

Certainly, feeding in an image will give you values at each neuron, but then how can we use that information to exaggerate details in the original image? I've struggled to find any detailed write-ups about this.

References:
Here vzn answered a similar question: https://cs.stackexchange.com/a/44857/49671

From that link, there is an implementation of Deepdream, here: http://auduno.com/post/125362849838/visualizing-googlenet-classes

Except it doesn't offer exaggeration of features as discussed here:http://googleresearch.blogspot.com/2015/06/inceptionism-going-deeper-into-neural.html

Where they both show the visualization of particular classes, and particular layers, and say:

  Instead of exactly prescribing which feature we want the network to
  amplify, we can also let the network make that decision. In this case
  we simply feed the network an arbitrary image or photo and let the
  network analyze the picture. We then pick a layer and ask the network
  to enhance whatever it detected.


texts: How can a universal Turing machine simulate "bigger" ones?

texts:
I'm trying to find the answers of two questions about the Universal Turing machine.

How can the Universal Turing machine simulate a Turing machine if
the one that is being simulated has a bigger number of states?
How can the Universal Turing machine simulate a Turing machine if
the one that is being simulated has a bigger number of alphabet
characters?

Can anyone help me with these questions?


texts:
Assume I have two Horn formulas $\phi_1, \phi_2$.   Horn formulas are CNF formulas so that each clause has at most one unnegated literal.  For example:
$x_1 \wedge (\neg x_1 \vee \neg x_2 \vee x_3 )\wedge (x_3 \vee \neg x_4)$
I want to decide whether $\phi_1,\phi_2$ are logically equivalent, i.e., $\phi_1 \leftrightarrow \phi_2$.  Equivalently, I want to test whether  $F=(\phi_1 \vee \neg\phi_2)\wedge (\neg \phi_1 \vee \phi_2)$ is true for all assignments of $x_1,\dots,x_n$.
Is this problem tractable?


texts:
Let assume that I have the following two automata A1 and A2 :

I have to do the intersection of the two, so I did this :

My question is related to the "∅". If I have two incomplete automata without dead states, and given a specific state, one automaton has a transition for one symbol but the second doesn't have it, what should I do ?
For example I am in the state 13 in the transition table and I read "b", should I rather put ∅ or 4 and make it non final ?


texts: Computing shifted fix point in the BSS model

texts:
Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is strictly convex, increasing, and continuous on the interval $[0,u]$.

Assume that we can compute $p(x)$ on $[0,u]$ and the inverse function $p^{-1}(y)$ on $[0,p(u)]$ exactly with indefinite precision via oracle calls. We assume that we are in the Blum-Shub-Smale model, in which we can handle real numbers within arbitrary precision.

That's all we have for $p$. The question is: Can we use the oracles for $p$ and $p^{-1}$ in order to solve an equation of the form $p(x) = x+c$ for some real $c > 0$ ? (that's what I mean with "shifted fix point") We are only interested in solutions in the interval $[0,u]$ and we know that there is one such solution (which is uniquely defined, as one can easily see).

Is there any possibility or is the problem uncomputable in the BSS model for general functions $p$ ?

As I know from this question, already equations of the form $x^2 - 2 = 0$ are not solvable even in the BSS model, such that $p(x) = x+c$ would not be possible to solve for $p(x) = x^2+x$ and $c=2$ without any further assumptions. However, it might still be possible to use the oracles in some elegant way in order to solve the equation.


texts: How to get an element from an existential proposition in Type theory proof assistant (Lean prover)

texts:
I am trying to implement set theory in type theory from scratch, just for self pedagogical purposes. Specifically, I'm using the Lean Prover, and defining the element-of relation from scratch using the symbol $\epsilon$, just for pedagogical purposes.

What I'm trying to do

However, I'm unsure how to even define the notion of inductive set in this way. I am using the definition of inductive set:

  a set $S$ is inductive if $\emptyset \in S \land \forall x\in S, x\cup \{x\} \in S$.
  The axiom of infinity then states that there exists an inductive set.

Where I'm getting stuck is at even defining the set $\{x\}$ in Lean. I know from the axiom of pairing, that there exists a set, which we denote by $\{x\}$, which is shorthand for $\{x,x\}$, such that $\forall u, (u\in \{x,x\} \iff u = x \lor u = x)$.

What goes wrong

However, in type theory this axiom doesn't give me the actual set, it gives me an inhabitant of the existential proposition type. I've tried to use the "let" command to extract from this the actual set, but I get the error: "invalid match/convoy expression, expected type is not known".
This makes me suspect I shouldn't be using this command here at all (I think it's only intended for proofs).

Maybe instead I should be using the axiom of choice?

My code

constant Set : Type
constant In : Set → Set → Prop
infix  `ε`:50  := In

axiom pairing : ∀X:Set, ∀Y:Set, ∃S:Set, ∀u, u ε S ↔ u = X ∨ u = Y
axiom union : ∀X, ∀Y, ∃S, ∀u, u ε S ↔ u ε X ∨ u ε Y
infix `U`:49 := union

definition inductiveset (S:Set) : Prop := ∀x:Set,
let ⟨ (Q:Set), (h: ∀u, u ε S ↔ (u = x ∨ u = x) ) ⟩ := (pairing x x) in
     x ε S → (x U Q) ε S

axiom infinity : ∃S, inductiveset S

Summary

So basically:

How do I actually define the inductive set property in Lean?
Can I just extract a function $f:X\to Y$ from proof of a proposition $\forall x:X,\exists y:Y, ...$?
should I use the axiom of choice here?

Edit: Defining an operation from an existence theorem.

unique existence case.
Suppose I have the following:

constant T:Type
constants P:T → T → Prop
axiom ....
......
%Now, after 5 pages of lemmas, I prove:
theorem uniqueexistence : ∀t:T, ∃u:T, ( P t u ∧ ∀v:T, ¬v=u → ¬(P t v) )
                        := λ t:T, complicated_proof lemma238 t

Suppose I have a Lean file like the one above, How do I then create an operator F:T → T together with a theorem that ∀t:T, P t (F t)?

nonuniqueness case.
Similarly, if instead I don't have uniqueness, how do I randomly pick such an operator?

theorem nonuniqueexistence : ∀t:T, ∃u:T, P t u
                        := λ t:T, complicated_proof lemma238 t

How do I randomly (using the axiom of choice) pick an operator F:T → T together with a theorem that ∀t:T, P t (F t)?


texts: Why is Big O not defined here for a hash table?

texts:
In this cheat sheet, average time complexity for access to a hash table is listed as N/A.

I'm curious as to why.  Since a hash table is mostly mathematical, I would assume it would be O(1) like the other operations ... Search, Insertion, Delete.

http://bigocheatsheet.com/


texts: What does it mean to be "independent of machine model"?

texts:
I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with subroutines or composition or something. My question is: What precisely does that mean? or, what precisely does it mean to be independent of the choice of machine model?

It makes sense to me that invariance under change of machine model - whatever that means - would make $\mathsf{P}$ a theoretically natural class to study, sort of the same way that Euclidean geometry is interested in the notions which are invariant under similarity, or linear algebra is interested in the notions which do not depend on a particular choice of basis. (The analogy is not entirely accurate, as those fields are only interested in such invariant notions, while computer science is still interested in properties of particular machine models.) While I understand what it means to be independent of the choice of basis, I don't understand what it means to be independent of the choice of machine model. Is there even a unique such concept, or are there several different concepts used in different contexts?

I've talked about $\mathsf{P}$ as a specific example, but what other commonly-studied ideas (in complexity theory or otherwise) are machine-independent in the same sense that $\mathsf{P}$ is? Are there ones that are not?

Thanks for helping to clear this up for me.


texts:
I'm looking for something i would call rating functions.
I'm searching for some literature about this concept.
I'm not really sure about the terminology, but what I mean should be pretty obvious.

A type of function that returns a rating of some input.

Lets have a function that gets some input and returns a number between 0 and 1 as a rating, where 0 is bad and 1 is great. Everything between is well between bad and great depending.

Lets assume inputs are just numbers

$f\colon \mathbb{N} \longrightarrow [0,1]$

I would like if I have several rating functions be able to compose them.
For example if I have the rating functions $r_1$, $r_2$ I would like to compose both to a new rating function that returns a new rating in dependency to $r_1$ and $r_2$

Now I'm looking for literature, but was unable to find any.
Can somebody hint me into the correct direction?
The correct name for the concept I'm looking for would be great.

Edit

I want to implement various Rating Functions and want to combine them

One functions could be

alwaysPerfect = (x) -> 1
alwaysBad = (x) -> 0
isOdd = (x) -> x%2
distanceToOne = (x) ->
  x = 2 if x is 0
  1/abs(x)

Anyone could implement this functions, but the contract for this functions would be to always return a value between 0 and 1

I need to evaluate some data with various evaluation conditions. Writing these evaluation seperate small functions and combine them seems to be more clearer than writing one big function that does all the evalauting


texts: I'm looking for efficient algorithm distributing atomic resources with arbitrar weight among a number of buckets with random capacity. Buckets can be added or removed, and resources from removed buckets should be redistributed among remaining ones. Are there any known algorithms solving this problem? Consider both situations when you can move already distributed resources and not.


texts:
It is well known that the S and K combinators form a basis set for combinator calculus, in the sense that all other combinators can be expressed in terms of them. There is also Curry's B, C, K, W basis, which has the same property. There must be an infinite number of such bases, but I don't know of any others.

I am aware that there are a number of single-combinator bases, such as the Iota combinator and the various others constructed/reviewed by Fokker. However, these are "improper" combinators, meaning that they are expressed in terms of other combinators rather than pure abstractions.1  For the purposes of this question I'm interested only in basis sets composed of proper combinators.

Does there also exist a study of the other possible basis sets? Ideal would be something along the lines of Wolfram's study of various other models of computation, in which the various combinations are studied systematically. In particular, I'm interested in whether simple examples of the following things are known:

A minimal basis set that includes the I combinator. (I'm using "minimal" to mean that if you remove any member it stops being a basis, so the SKI basis would not count.)
A minimal basis set that includes the Y combinator, or the $\omega$ combinator (aka mockingbird)

Any other information about other possible bases for combinatory logic besides S, K and B, C, K, W would be really helpful.

As a broader point, I'm interested in the study of the combinatory calculus as a purely mechanical system, i.e. as a set of transformation rules on binary trees with labelled nodes, which need not be given any particular semantic interpretation. Any pointers towards resources that take this approach would be greatly appreciated. (To Mock a Mockingbird takes this approach but gives an incomplete presentation, whereas Barendregt's the Lambda Calculus is very much tied to semantics, making it hard for me to extract the purely mechanical aspects that I'm interested in.)

1To be precise: in lambda calculus a proper combinator is an expression of the form $(\lambda.x_1x_2\dots P(x_1,x_2,\dots))$, where $P(x_1,x_2,\dots)$ only has $x_1$, $x_2$ etc. as free variables, and does not contain any abstractions. So for example, $(\lambda x y z. x(z z))$ is a proper combinator, but $(\lambda x. x(\lambda y.y) )$ is not, because it contains $x$ applied to a lambda term.


texts: Resources about implementing a database table

texts:
I'd like to understand more how data can be stored on disk so it can be read quickly. I don't want to say database record because I'm not asking how to build a database. My question is closer to how would I build a table.
I'm not asking about indexing. I'm thinking about you have an application that already has some a pointer to a record.
I've been trying to find some references e.g. papers, books, but everything so far focuses on database design as in writing DDL or structures for indexing like B+ trees.
Are there any references that talk about how tables are actually implemented and what are the tradeoffs?


texts: The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

texts:
In the Floyd-Warshall algorithm we have:

Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\{1, 2, \cdots, k\}$ then

\begin{align*}
&d_{ij}^{(k)}= \begin{cases}
w_{ij} & \text{ if } k = 0 \\
\min\{d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\} & \text{ if } k > 0
\end{cases}\\
\end{align*}

In fact it considers whether $k$ is an intermediate vertex in the shortest path from $i$ to $j$ or not. If $k$ is an intermediate it selects $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ becuase it decomposes the shortest path to  $i \stackrel{p_1}{\leadsto} k \stackrel{p_2}{\leadsto} j$  otherwise $d_{ij}^{(k-1)}$ since $k$ is not an intermediate vertex so it has no effect on the shortest path.

My problem is, For a given shortest path between $i$ and $j$, $k$ is an intermediate vertex or not and its existence is deduced from the structure of the graph not our decision. so we have no freedom to select or not to select the $k$, because if $k$ is an intermediate vertex so we must choose $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ and if not we must choose $d_{ij}^{(k-1)}$. But when in formula it takes $\min$ between two numbers, it sounds like that it has option to select any of them while based on the structure of the graph there is no option for us. I believe the formula must be

\begin{align*}
&d_{ij}^{(k)}= \begin{cases}
w_{ij} & \text{ if } k = 0 \\
d_{ij}^{(k-1)} & \text{ if } k > 0 \text{ and } k \notin \text{ intermediate}(p)\\
d_{ik}^{(k-1)} + d_{kj}^{(k-1)} & \text{ if } k > 0 \text{ and } k \in \text{ intermediate}(p)
\end{cases}\\
\end{align*}


texts:
A genral Turing model with one tape to define sublinear space (L,NL,..)
Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and a work tape; or often three: with an additional output tape. (We do this because the reading of the input would cost us linear space.)
I'm looking for a general Turing model with just one tape and one consistent definition for space and for complexity that works in all the cases, inclusively the sub-linear case of L (Logspace), NL (NLogspace).. and the more famous P, NP, PSPACE etc.
For this purpose obviously we must change the space definition - but how best?
EDIT: For example: if we just count the new written cells in a one-tape machine would this solve the problem?


texts:
I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the
$\mathsf{PATH}$ problem (decide whether a graph $G$ has a path from a given node $s$ to another given node $t$) which is complete for $\mathbf{NL}$ is also contained in $\mathbf{NC}$ (this is easy). The question then also makes a remark that this implies that $\mathbf{NL} \subseteq \mathbf{NC}$ which is not obvious to me.

I think in order to show this, one has to show that $\mathbf{NC}$ is closed under logspace reductions, i.e

$$(1): B \in \mathbf{NC} \hbox{ and } A \le_l B \Longrightarrow A \in \mathbf{NC}$$

where $\le_l$ is the logspace reduction defined as

$$A \le_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)[x \in A \Longleftrightarrow M(x) \in B]$$

($M$ is a TM which runs in logarithmic space).

I would appreciate if someone could give a tip for proving the statement $(1)$.


texts: How can a Number Represented without Normalization Technique?

texts:
Consider the following floating point Representation

Mantissa is pure fraction in signed magnitude form . What is the representation of the binary number 1111.1111 $\times 2^{2} $ in hexadecimal without Normalization .

My Approach

bias = 64

$(-1)^{S} (1.M)_{2} \times 2^{\text{E-bias}}$  This is normalized Representation .

But here we are asked to find the Not Normalized Representation that means we need to store    1111.1111 $\times 2^{2} $ as such . But How can this be done ?

$1.1111111 \times 2^{5}$

Do I need to add bias when storing in Not Normalized form ?

here bias is 64 (excess 64 representation) i.e Sign is 0 , Exponent will be 69 and Mantissa is 255 [ this is same as Normalized Representation]

OR Do Not need to add bias and store number as it is ?

here , Sign is 0 , Exponent will be 5 , Mantissa will be 255

Please confirm which is the correct Representation give some links to online resources stating the correctness of the approach as well


texts: Degrees of polynomials representing Boolean functions

texts:
Let $$B_1=\vee_{i_1=1}^d\wedge_{i_2=1}^d\dots\vee_{i_{2r-1}=1}^d\wedge_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$
$$B_2=\wedge_{i_1=1}^d\vee_{i_2=1}^d\dots\wedge_{i_{2r-1}=1}^d\vee_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$ be two boolean functions in $d^{2r}$ variables $X_{i_1i_2\dots i_{2r-1}i_{2r}}$ that take values in$\{0,1\}$.

Let $Z_0(B_i)$ be the set of $\{0,1\}^{d^{2r}}$-tuples that $B_i$ takes $0$.
Let $Z_1(B_i)$ be the set of $\{0,1\}^{d^{2r}}$-tuples that $B_i$ takes $1$.

Let $f_1,f_2,g_1,g_2$ be polynomials in $d^{2r}$ variables that satisfy:

$(1)$ For every $z\in Z_0(B_i)$, $f_i(z)=g_i(z)=0$

$(2)$ For every $z\in Z_1(B_i)$, $f_i(z)=1$ and $g_i(z)\neq0$.

What is the smallest total degree of each $f_1,f_2,g_1,g_2$?


texts: Is Knapsack restricted to integers between 1 and 100 still NP-complete?

texts:
The title pretty much says it all. I want to know if Knapsack is still NP-complete when the weights, values, and weight limit are restricted to a finite set of values. I figure that it wouldn't be because clearly for very small finite sets it isn't. (E.g., if you must use integers from 1 to 3.) That said, I'm struggling to find a polynomial-time algorithm.

One thought I had was since there are a finite set of possible inputs and outputs, could your algorithm just be a massive chain of if statements? I'm not sure whether this even would count as an "algorithm" though.


texts: Algorithm to determine if an interval is covered by a list of intervals?

texts: Given a list of intervals $[s_1, e_1], [s_2, e_2], \ldots$, what's the most efficient way to determine if an interval $[a, b]$ can be covered by the intervals in the list?


texts: What other than programming does a computer science degree usually involve?

texts:
Programming courses are about 30% of my computer science degree. Also at my university, around 15-20% of the degree are applied math courses.

What other areas/fields are covered? For the majority of ABET accredited universities?

The question that inspired this post was "should i study computer science if I'm only interested in programming at this point?"


texts: In automata theory, we all read automata as finite automata, from the very beginning. What I want to know is, why are automata finite? To be clear, what is it in an automaton that is finite - the alphabet, language, strings made with regular expressions, or what? And are there (in theory) any non-finite automata?


texts:
So, this might be a really simple problem but I can't seem to find a nice algorithm to solve it:

  Given two ranges, [a1, a2], [b1, b2]  (all real numbers) and a real number n, find the length of the overlapping segment between the two ranges over a modulo of n.

For example, consider a 24-hour clock and the range [20, 4] (night time); for a given range, calculate the number of hours within that range that are night hours:

[13, 21] ==> 1 #[20,21]

[0, 6] ==> 4 #[0, 4]

[11, 19] ==> 0

I tried to think of it in terms of predefined segments
[a1,b1], [b2, a2] and do some math with them but it didn't work.
Maybe I should sort them somehow?

I will appreciate any help or direction, thanks!


texts: Reason for global update steps in the push-relabel algorithm

texts: I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?


texts:
What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?