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

The problem (are there items such that all except the largest fit, and the total value is ≥ V) is obviously in NP. It is also NP complete because we can use it to solve Knapsack: Given a knapsack problem, add an item with sufficiently large weight w, and sufficiently large value v, solve the problem with V + v, and the solution with the large item removed ...


2

Let me tell you the road map. First thing you need to learn is discrete mathematics, try some books at your own. Once you are comfortable with discrete mathematics then again go through data strcurures one more time. Once you are ok with data structure. Its time to learn the algorithms from coreman book or from any other book. Now once you have a learned ...


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 ...


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$ ...


1

After a little bit of struggling I found an easy answer by myself: We can "define" a ternary relation: $T(x,y,z) \equiv M(x,y) \land M(y,z) \land M(z,x)$ Then we can define $L$ in this way: $\exists M$ such that $\forall x,y \;.\; U_a(x) \land U_b(y) \to x < y$ ($a$s before $b$s) $\forall z \;.\; U_b(z) \to \exists x, y \;.\; U_a(x) \land U_a(y) \land ...


1

If you're looking to increase your development skills, a more hands-on approach to Automata, Automata and Computability: A Programmer's Perspective is an easy read that comes with a fantastic visualization tool for many topics in the field: DFA, NFA, PDA, TM, etc. It's great for getting your feet wet with developing general automata, IMO.


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