We’re rewarding the question askers & reputations are being recalculated! Read more.
9

If the truth value of a formula is determined by setting only a subset of the variables, an author might skip describing the remaining truth values. However, by definition, a truth assignment gives a value to every variable.


8

A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom. The following is a proof taken from this note by Rob van Glabbeek. Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. Proof: By a reduction of post correspondence problem (...


6

You want to write some executable code (is_left_restartable) and use it inside a type annotation. This is, by definition, a dependent type. The problem when you have dependent types is that it's hard to keep type checking usable for a programming language. It's generally desirable to keep the type system decidable, because programmers tend to be annoyed ...


6

Yes, realizability theory allows you to model dependent type theory based on a variety of computational models, such as: Turing machines (with or without oracles), various $\lambda$-calculi, topological models of computation, sequential functionals, game-semantics computational models, and many others. References: Jaap van Oosten: Realizability: an ...


5

This will be a partially inconclusive answer, unfortunately. Hopefully someone more knowledgeable can chime in and confirm the missing details. Let me summarize what I could find out so far. Nondeterministic automata were introduced by Rabin and Scott in 1959. They also define two-way automata (which is a prelude to the LBAs introduced by Myhill the ...


4

For concurrency in general, there is a very active line of research, which I tried to summarise in this reply: https://cs.stackexchange.com/a/102711/98901 I add here a comment on parallelism, below. Avron [1996] introduced the notion of hypersequents, i.e., collections of sequents in judgements. In [Kokke et al., 2019], we showed that a conservative ...


4

First of all, the definition of weakest precondition you've mentioned might be a little bit confusing. Namely, remember that the weakest precondition, designates all states of a program, such that when the given command executes, the given postcondition is satisfied. Therefore, your initial definition might be a bit confusing, in the sense that the weakest ...


4

What you are searching for could be Some Estimated Likelihoods For Computational Complexity by R. Ryan Williams, 2018. Here are "Some Estimated Likelihoods for Some Major Open Problems" in that paper. Note that "The numerical values of my 'estimated likelihoods' are (obviously) nothing too rigorous. What is more important is the relative measure between ...


3

Consider a subPCA $A$ of Kleene's first algebra. It contains $K$ and $S$. These are sufficient to implement every total computable function, so $A$ must contain at least these, and cannot be just some limited complexity class. I do not quite understand why Kleene's second algebra and Scott's graph model aren't "topological". Kleene's second algebra is the ...


3

Perhaps you are looking for the diagram on slide 12 of this talk by Scott Aaronson. Scott has given the talk many times, and not all versions contain the slide. Note that except for P vs NP, it does not contain any open problems, but apart from that, it appears to match your description.


3

The paper you are asking for is: Patterson, David A; Ditzel; David R: The case for the Reduced Instruction Set Computer, Computer Architecture News, 8(6):25-33, Oct 1980. (non-paywalled copy). Beware that it may be the paper you are asking for, but may not be the paper you want. Almost everything it says is false, or has been debunked. It is more of a ...


3

I would say that this approach falls under the umbrella of iterative rounding. I believe that the seminal paper regarding this kind of strategy is [1]. The heuristic outlined here differs in signifcant ways from the algorithm described in Jain's paper but I think the basic idea is in the same vein. Jain, K. (2001). A factor 2 approximation algorithm for the ...


3

This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.


3

In "Extensions of some theorems of Gödel and Church" it's shown by Barkley Rosser that these sets are exactly the recursive sets: Corollary I. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function. Note that the crux here is repetitions. Since you ...


3

First off, I assume you also want to have a binary relation on the domain, acting as a linear order: <. Furthermore, I assume you want to deal with existential second-order logic, which in general allows more than one existential quantifiert. Then, you can employ Fagin's theorem: wikipedia And what remains to show is that you can recognize the language $...


2

We will reduce Vertex Cover to Edge Dominating Set and complete the proof. Given an instance of the decision version of vertex cover problem $I(G,k)$, we construct $G'$ by adding $nk+k$ new edges to $G$, where $n$ is the number of vertices in $G$: add $k$ new vertices; add an edge between each of these new vertices and each vertex in $G$, totally $nk$ ...


2

The other day I was reading a paper on parallelized random access machines without bit operations, which sounded very much like what you are describing. For these models NC is known not to equal P. See here: https://epubs.siam.org/doi/10.1137/S0097539794282930 The paper can also be found on Professor Mulmuley’s website.


2

There are many algorithms that uses the divide-and-conquer paradigm besides merge sort and quicksort. "There is no accepted formal definition of the divide and conquer paradigm, and so we must regard this paradigm as an informal concept.", reads an answer by Yuval Filmus. I will use Wikipedia entry on divide-and-conquer as the reference to interpret its ...


2

Please skip that article at tutorialspoint. Instead, read this article at GeekforGeeks, which is much better. You may want to check my answer to another question. The common abbreviations for Left rotation, Right rotation, Left-Right rotation, Right-Left rotation are L, R, LR and RL respectively, as expected. These rotations can be applied to all kinds of ...


2

You can reduce graph isomorphism on directed graphs to graph isomorphism on undirected graphs. I think it's possible to build a reduction that preserves the bounded-degree property. For instance, I think the following should work. Replace each directed edge u --> v with the following gadget: u --- a --- c --- v | b where a, b, and c are ...


2

Not a complete answer, but in T. Kloks Treewidth you have the following lemma: There always exists a nice tree decomposition of width $k$ and with at most $4n$ bags. It is NP-complete to determine the minimum number of bags in a tree decomposition of width $k$.


2

After searching around for paper some more (unfortunately, I found nothing in Ling Liu, M. Tamer Özsu eds. Encyclopedia of Database Systems), I managed to find out that these dependencies are called numerical dependencies. In particular, standard notation for my $\mathcal{A} \rightrightarrows^k \mathcal{B}$ is $\mathcal{A} \xrightarrow{k} \mathcal{B}$, which ...


2

Finding the minimal energy configuration in the Ising model is NP-hard, and many problems can be directly reduced to it. For a list, including Karp's original 21 NP-hard problem see e.g. Ising formulations of many NP problems. The Ising model is also equivalent to unconstrained quadratic binary optimization which also can be used to model a large number of ...


2

You can find a definition in Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman, in the fourth chapter. Here's a link : HMU, the section begins at page 171 of the pdf Two DFA are said to be equivalent if they accept the same language, and (an equivalent proposition) if they have the same minimal automaton (which is unique).


2

Start with an arbitrary PDA. Convert it to a PDA which pushes at most two symbols to the stack at each step — this only incurs a linear blow-up. Convert the PDA to a CFG using the standard construction, described in this answer. Since the PDA pushed at most two symbols at each step, the CFG has size $O(n^3)$ (for each transition $p \stackrel {a,\gamma} ...


2

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle ...


2

Two old, but, I think, still very useful resources: M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to what you are asking about, download for free: link. S.G.Akl, K.A.Lyons. Parallel Computational Geometry. Prentice-Hall, 1993 - monograph about first ten years of ...


2

Simply pick up any algorithms book out there, they will all take you through these things. What you are describing is essentially the algorithms (and computational complexity) field. The most popular books are Algorithms by Sedgewick and Wayne, which is free for download, the CLRS Introduction to Algorithms, and the epic Art of Computer Programming by ...


2

I just found the answer myself. In this paper: Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs‏". Technical reports, HP research labs. in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,\ldots,s$ edges. The ...


2

Theory of Computation, as practiced in the US, focuses mainly on two areas: algorithms and complexity. For algorithms, the standard textbook is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, also known by its acronym CLRS. For complexity, there's the advanced textbook Computational Complexity: A Modern Approach, but it might be too much ...


Only top voted, non community-wiki answers of a minimum length are eligible