All Questions

46,332 questions
Filter by
Sorted by
Tagged with
2 views

Valid Arguments

Is the following argument valid? If Helen gets the supervisor’s position, then she’ll buy a new car. She has purchased a new car. Therefore, Helen did get the supervisor’s position. Consider the ...
2 views

Simplifying expressions with justifications (L.M*)*

Try to simplify the following expressions and justify your simplification. $$(iii) (L+M^*)^*$$ $$(iv) (L.M^*)^*$$ I think the first one can be simplified as (L+M)* but couldn't figure out the ...
• 55
6 views

How to develop intuition to come up with Context Free Grammar?

So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam. one of the question is to give context free grammar for these two languages and the ...
• 1
16 views

Is it better to arrange datatypes in a computer programme using arrays or linked lists?

How should datatypes be organised in a computer programme? Is it better to utilise arrays or linked lists? I'm not sure what the difference is, but I seem to recall hearing that arrays are quicker. Or ...
• 11
4 views

Is there a sorting program or formula to sort and place individuals in classes based on preferences

I am looking for a formula or program to help place people in classes based on their preferences. The elements of the problem are: There are 30 class choices a student can pick from. There are 400 ...
7 views

Computational complexity of some optimization problem?

I wonder if there are some methods I can borrow from computational complexity theory to analyze the optimization problem such as a convex optimization problem. An example of this is to find the ...
• 51
12 views

Complexity of generating all subsets of size $k$ using recursion

What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set? ...
• 123
8 views

• 304
18 views

Threads and its priority in Java

I was experimenting with the concept of threading in java, we have a method setPriority, using which we can set thread priority. In official documentation it is given as below, But while seeing in ...
37 views

1 vote
40 views

Reconstructing a string from two its partitions into substrings of varying size

Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice. Under an ...
30 views

Does a non-deterministic Turingmachine reach every possible result?

I have problems to imagine a non-deterministic Turingmachine. Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether ...
1 vote
21 views

SMT solver gives up on seemingly trivial problem

I expected CVC5 to produce a proof given the following problem in TPTP format. Why does CVC5 give up on the TPTP problem, but works just fine on the same problem given in SMT-LIB2? In human words, the ...
18 views

[Disclaimer: Crossposted in cstheory --> Link] In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [...
9 views

Is there a way to modify the DK Test for DCFGs to test for ambiguity of CFGs?

I am currently reading Sipser's book on the Theory of Computation, and was wondering about the the question in the title. Here is my current understanding of the concepts: A deterministic context free ...