We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both (...) classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (shrink)

Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of forbidden (...) induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from $\varphi $ the corresponding forbidden induced subgraphs. This machinery fails on finite graphs as shown by our results: – There is a class $\mathscr {C}$ of finite graphs that is definable in first-order logic and closed under induced subgraphs but has no finite set of forbidden induced subgraphs. – Even if we only consider classes $\mathscr {C}$ of finite graphs that can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from a first-order sentence $\varphi $ that defines $\mathscr {C}$ and the size of the characterization cannot be bounded by $f(|\varphi |)$ for any computable function f. Besides their importance in graph theory, the above results also significantly strengthen similar known theorems for arbitrary structures. (shrink)

Leonid Levin showed that every algorithm computing a function has an optimal inverter. Recently, we applied his result in various contexts: existence of optimal acceptors, existence of hard sequences for algorithms and proof systems, proofs of Gödel’s incompleteness theorems, analysis of the complexity of the clique problem assuming the nonuniform Exponential Time Hypothesis. We present all these applications here. Even though a simple diagonalization yields Levin’s result, we believe that it is worthwhile to be aware of the explicit result. The (...) purpose of this survey is to convince the reader of our view. (shrink)

Assume that the problem P0 is not solvable in polynomial time. Let T be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{ConT} as the minimal extension of T proving for some algorithm that it decides P0 as fast as any algorithm B with the property that T proves that B decides P0. Here, ConT claims the consistency of T. As a byproduct, we obtain a version of Gödelʼs Second Incompleteness Theorem. Moreover, we characterize problems (...) with an optimal algorithm in terms of arithmetical theories. (shrink)

The undecidability of first-order logic implies that there is no computable bound on the length of shortest proofs of valid sentences of first-order logic. Some valid sentences can only have quite long proofs. How hard is it to prove such "hard" valid sentences? The polynomial time tractability of this problem would imply the fixed-parameter tractability of the parameterized problem that, given a natural number n in unary as input and a first-order sentence φ as parameter, asks whether φ has a (...) proof of length ≤ n. As the underlying classical problem has been considered by Gödel we denote this problem by p-Gödel. We show that p-Gödel is not fixed-parameter tractable if DTIME(h O(1) ) ≠ NTIME(h O(1) ) for all time constructible and increasing functions h. Moreover we analyze the complexity of the construction problem associated with p-Gödel. (shrink)

Many parameterized problems ask, given an instance and a natural number k as parameter, whether there is a solution of size k. We analyze the relationship between the complexity of such a problem and the corresponding maximality problem asking for a solution of size k maximal with respect to set inclusion. As our results show, many maximality problems increase the parameterized complexity, while “in terms of the W-hierarchy” minimality problems do not increase the complexity. We also address the corresponding construction, (...) listing, and counting problems. (shrink)

This paper examines the market response to the events leading up to the passage of Section 1502 of the Dodd-Frank Wall Street Reform and Consumer Protection Act to explore whether investors value mandatory human rights disclosures of conflict mineral usage. Using a sample of 3639 US registrants from January 1, 2008 to September 30, 2014, we document a significant negative stock market reaction to the passage of the Act. Using a sample of 1206 filers, we also find a negative market (...) reaction to conflict mineral disclosures under the Act. The market reaction is more negative and limited to companies that source their minerals from the DRC and adjoining countries, companies with prior records of human rights violations, and companies with ambiguous disclosures. However, the market appears to reward firms that use risk-mitigation strategies. This paper provides preliminary evidence that the mandatory disclosure of conflict mineral information on Form SD poses a threat to firms’ legitimacy, resulting in a net cost to investors. The results of this study provide economic justification for companies with poor records of conflict mineral sourcing to improve their practices for the purpose of avoiding the high costs that will arise if they are forced to disclose human rights abuses related to conflict mineral use. (shrink)

We observe that the W*-hierarchy, a variant (introduced by Downey, Fellows, and Taylor [7]) of the better known W-hierarchy, coincides with the W-hierarchy, though not level wise, but just as a whole hierarchy. More precisely, we prove that W[t] ⊆ W*[t] ⊆ W[2t − 2] for each t ≥ 2. It was known before that W[1] = W*[1] and W[2] = W*[2]. Our second main result is a new logical characterization of the W*-hierarchy in terms of "Fagin-definable problems." As a (...) by-product, we also obtain an improvement of our earlier characterization of the hierarchy in terms of model-checking problems. Furthermore, we obtain new complete problems for the classes W[3] and W*[3]. (shrink)

To probe the motivational roles of hedonic gratification and social gratification in giving “Like” feedback on social media, we developed a set of novel pictures to simulate WeChat Moments. We subsequently examined how the personality trait of extraversion and stimulus content characteristics influenced “Liking” behavior. A 2 × 3 × 2 -mixed experimental design was applied to data obtained from 56 WeChat Moments users. These participants included 28 individuals with the highest extraversion scale scores, and 28 individuals with the lowest (...) extraversion scale scores, according to the NEO Five-Factor Inventory. Briefly, participants observed pictures on an interface similar to that of WeChat Moments and were given the option to “Like” each picture. “Like” rates and response time were then compared across groups and conditions by applying a mixed-design analysis of variance. Pearson's correlation coefficients were calculated to explore relationships between the “Like” rates under each condition and the scores for each personality trait. Compared with the neutral pictures, the positive and negative pictures were “Liked” more and less frequently, respectively. Compared with the poster-unrelated pictures, the personally related pictures were “Liked” more frequently. In the extrovert group, the frequency of “Likes” given to unrelated negative content positively associated with neuroticism and negatively associated with conscientiousness. No correlations were observed in the introvert group. Compared with not giving “Like” feedback, participants gave “Likes” to positive and negative pictures more quickly and slowly, respectively.These results support the hypothesis that hedonic gratification and social gratification motivate “Like” feedback for positive content and personally related content, respectively. “Liking” behavior was not affected by extraversion, but was related to neuroticism and conscientiousness. Content-related differences in time intervals for giving “Like” feedback in this study suggest that people do not hesitate to give “Like” feedback to positive content on WeChat Moments, yet linger in deciding to give “Like” feedback to negative content. (shrink)