# All Questions

11,368 questions
Filter by
Sorted by
Tagged with
63 views

### Proving NP-complete problem

Suppose the following problem: Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is ...
271 views

1k views

### why is a Turing machine defined as a 5-tuple? [closed]

[Edited to provide better context.] In a comment on meta, JɛﬀE suggested that this would be a good topic for a question to ask here. why is a Turing machine defined as a 5-tuple?
623 views

### Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
256 views

### Does a Non deterministic TM halt after the same number of steps on the same input? [closed]

Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt. If $M$ is a deterministic TM, it will ...
382 views

### Theoretical Computer Science or Sensor Networks

I am a first year PhD student in computer science. The major areas my supervisor is working with are: Theoretical Computer Science (knowledge representation, uncertainty, etc.) and wireless sensor ...
3k views

### Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
1k views

### Alternative Turing Machine Proofs

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me. I am looking for a TM Halting Problem proof that ...
76 views

### We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q? [closed]

Exact-Cover-by-3Sets (X3C) is NP-complete. If the number of classes i.e. |C|<2q then whether this is version of X3C is NP-complete or not?
4k views

### Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
745 views

### Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
314 views

### whats the difference between nondeterminism and parallelism? [closed]

pondering another Q/A & the responses on here[1] leads to this question: whats the difference between nondeterminism and parallelism? am aware of basic answers. have some of my own ideas on ...
981 views

### Proof of correctness of in-place Quick sort

I have found proof of correctness of Quick sort (not in-place version), Please refer me a proof of correctness of in-place Quick sort, or provide proof here is very appropriated. a typical ...
659 views

### Is halting that hard? [Yes] [closed]

I want to make a modification to the halting problem. The output now has two possibilities: This program halts and it does not have the crossing structure (defined below); This program does not halt ...
990 views

### Polynomial time algorithm to solve the TSP on an m by n solid grid

Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such ...
199 views

### A sandwich Algorithm / Data Structure [closed]

$O(n^c)$ is asymptotically greater than $O(\log^d n)$ for all possible pair of values of $c$ and $d$. Can you give an example of a problem (or data structure) which has running time (or query/...
126 views

### NP hard? Maximize the average for a subset of numbers

Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard? I think so, but I cannot come out with a proof. Thanks a ...
143 views

### Are there proofs which show that AIs are bound to be “worse” than the human brain? [closed]

I was talking with two PhDs (both teach IT related subjects) about artificial intelligence the other day. They were in agreement that an AI can never reach the level of the human brain, but failed to ...
148 views

### Do irrational number contain infinate/every patterns of sequences? [closed]

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
1k views

### Deterministic CFL closure Property Homomorphism [closed]

I tried to research the following question with no results: Can you find one example where the following holds true: Let L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx ...
23 views

### Help find algorithm for array-based task

Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)? What is the solution? My solution is not ...
120 views

### Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
26 views

### Polynomial-time reducibility of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
374 views

### Does any DAG can be topologically sorted? [closed]

I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. The key point is that before getting them into database, I need run "topological sort" in ...
160 views

### Dance Partner Problem NP-completeness [closed]

I really can't think of a concise way to phrase this problem, which makes it hard to search for, so forgive me if this is a duplicate question. I've come across a problem and I would like to know if ...
129 views

### non deterministic algorithm always find the right solution? [closed]

i'm confused since i see some books mention the NP time algorithms as "very lucky" that means it always finds the right path? also can someone explain the coming points to me please... A ...
130 views

### A simple challenge

Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. ...
241 views

### Some questions (still) unresolved about braids?

I was looking for interesting questions pertaining to braid theory. I don't know if the following are considered important, but I'd like to ask: (1) in relation with the following link, is it true ...
251 views

### Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...
691 views

### open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?
332 views

### Attacking TSP via small nonintersecting circuits

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted ...
372 views

### How can I call functions that are not “first-class functions”?

I mean, is there an antonym for "first-class function"?
27k views

### Application of calculus in computer science

Where are derivatives and integrals used in the field of Computer Science? What are their applications?
### What function has the signature $A \times \left ( B + C \right ) \rightarrow \left ( A \times B \right ) + \left ( A \times C \right )$?
$A \times \left ( B + C \right )$ is isomorphic to $\left ( A \times B \right ) + \left ( A \times C \right )$, right? That means there's a function from one to the other and another function back....