D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.

A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-complete.

We have shown the plausibility of considering time as a Fuzzy concept instead of classical time [7], [8]. By considering time as a fuzzy concept, we will have new classes of Complexity. Here, we show that how some famous problems will be solved in this new picture.

We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either (...) by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs. (shrink)

Let g be a map defined as the Nisan–Wigderson generator but based on an NP ∩ coNP -function f. Any string b outside the range of g determines a propositional tautology τb expressing this fact. Razborov [27] has conjectured that if f is hard on average for P/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. We consider a more general Statement that the tautologies have no polynomial size proofs in any propositional proof system. (...) This is equivalent to the statement that the complement of the range of g contains no infinite NP set. We prove that Statement is consistent with Cook' s theory PV and, in fact, with the true universal theory T PV in the language of PV. If PV in this consistency statement could be extended to "a bit" stronger theory then Razborov's conjecture would follow, and if TPV could be added too then Statement would follow. We discuss this problem in some detail, pointing out a certain form of reflection principle for propositional logic, and we introduce a related feasible disjunction property of proof systems. (shrink)

An NP-hardness proof for non-local Multicomponent Tree Adjoining Grammar (MCTAG) by Rambow and Satta (1st International Workshop on Tree Adjoining Grammers 1992 ), based on Dahlhaus and Warmuth (in J Comput Syst Sci 33:456–472, 1986 ), is extended to some linguistically relevant restrictions of that formalism. It is found that there are NP-hard grammars among non-local MCTAGs even if any or all of the following restrictions are imposed: (i) lexicalization: every tree in the grammar contains a terminal; (ii) dominance (...) links: every tree set contains at most two trees, and in every such tree set, there is a link between the foot node of one tree and the root node of the other tree, indicating that the former node must dominate the latter in the derived tree. This is the version of MCTAG proposed in Becker et al. (Proceedings of the 5th conference of the European chapter of the Association for Computational Linguistics 1991 ) to account for German long-distance scrambling. This result restricts the field of possible candidates for an extension of Tree Adjoining Grammar that would be both mildly context-sensitive and linguistically adequate. (shrink)

Local deterministic string-to-string transductions arise in natural language processing (NLP) tasks such as letter-to-sound translation or pronunciation modeling. This class of transductions is a simple generalization of morphisms of free monoids; learning local transductions is essentially the same as inference of certain monoid morphisms. However, learning even a highly restricted class of morphisms, the so-called fine morphisms, leads to intractable problems: deciding whether a hypothesized fine morphism is consistent with observations is an NP-complete problem; and maximizing classification accuracy of the (...) even smaller class of alphabetic substitution morphisms is APX-hard. These theoretical results provide some justification for using the kinds of heuristics that are commonly used for this learning task. (shrink)

Worries about scientific objectivity seem never-ending. Social critics and philosophers of science have argued that invocations of objectivity are often little more than attempts to boost the status of a claim, while calls for value neutrality may be used to suppress otherwise valid dissenting positions. Objectivity is used sometimes to advance democratic agendas, at other times to block them; sometimes for increasing the growth of knowledge, at others to resist it. Sandra Harding is not ready to throw out objectivity quite (...) yet. For all of its problems, she contends that objectivity is too powerful a concept simply to abandon. In Objectivity and Diversity, Harding calls for a science that is both more epistemically adequate and socially just, a science that would ask: How are the lives of the most economically and politically vulnerable groups affected by a particular piece of research? Do they have a say in whether and how the research is done? Should empirically reliable systems of indigenous knowledge count as "real science"? Ultimately, Harding argues for a shift from the ideal of a neutral, disinterested science to one that prizes fairness and responsibility. (shrink)

People in our liberal pluralistic society have conflicting intuitions about the legitimacy of coercive hard paternalism, though respect for agency provides a common source of objection to it. The hard paternalist must give adequate reasons for her coercion which are acceptable to a free and equal agent. Coercion that fails to meet with an agent’s reasonable evaluative commitments is at least problematic and risks being authoritarian. Even if the coercer claims no normative authority over the coercee, the former still uses (...) coercion to replace the latter’s reasons or will with his own reasons or will. But does every hard paternalistic view have to invite such objection? Throughout I will assume that defenders of what I will call “Neutral Paternalism” (NP) and “Commonsense Paternalism” (CP) aim to offer reasons for coercion all can reasonably endorse despite evaluative diversity, in opposition to more objectionable forms of coercive paternalism, such as those which defend it on religious or perfectionist grounds. I will argue, nonetheless, that Gerald Dworkin’s defense of NP and Danny Scoccia’s defense of CP succumb to the same problems of objectionable imposition that saddle other forms of coercive paternalism. The shortcomings in their views suggest that even modest hard paternalism is nonetheless problematic for liberals. (shrink)

We propose a technical reformulation of the measurement problem of quantum mechanics, which is based on the postulate that the final state of a measurement is classical; this accords with experimental practice as well as with Bohr’s views. Unlike the usual formulation (in which the post-measurement state is a unit vector in Hilbert space), our version actually opens the possibility of admitting a purely technical solution within the confines of conventional quantum theory (as opposed to solutions that either modify this (...) theory, or introduce unusual and controversial interpretative rules and/or ontologies). To that effect, we recall a remarkable phenomenon in the theory of Schrödinger operators (discovered in 1981 by Jona-Lasinio, Martinelli, and Scoppola), according to which the ground state of a symmetric double-well Hamiltonian (which is paradigmatically of Schrödinger’s Cat type) becomes exponentially sensitive to tiny perturbations of the potential as ħ→0. We show that this instability emerges also from the textbook wkb approximation, extend it to time-dependent perturbations, and study the dynamical transition from the ground state of the double well to the perturbed ground state (in which the cat is typically either dead or alive, depending on the details of the perturbation). Numerical simulations show that adiabatically arising perturbations may (quite literally) cause the collapse of the wave-function in the classical limit. Thus, at least in the context of a simple mathematical model, we combine the technical and conceptual virtues of decoherence (which fails to solve the measurement problem but launches the key idea that perturbations may come from the environment) with those of dynamical collapse models à la grw (which do solve the measurement problem but are ad hoc), without sharing their drawbacks: single measurement outcomes are obtained (instead of merely diagonal reduced density matrices), and no modification of quantum mechanics is needed. (shrink)

Transitive proxy voting (or "liquid democracy") is a novel form of collective decision making, often framed as an attractive hybrid of direct and representative democracy. Although the ideas behind liquid democracy have garnered widespread support, there have been relatively few attempts to model it formally. This paper makes three main contributions. First, it proposes a new social choice-theoretic model of liquid democracy, which is distinguished by taking a richer formal perspective on the process by which a voter chooses a proxy. (...) Second, it examines the model from an axiomatic perspective, proving (a) a proxy vote analogue of May's Theorem and (b) an impossibility result concerning monotonicity properties in a proxy vote setting. Third, it explores the topic of manipulation in transitive proxy votes. Two forms of manipulation specific to the proxy vote setting are defined, and it is shown that manipulation occurs in strictly more cases in proxy votes than in classical votes. (shrink)

Every generation re-writes history in its own way'. Re-writing History applies Collingwood's dictum to a series of topics and themes, some of which have been central to prehistoric and protohistoric archaeology for the past century or more, while some have been triggered by more recent changes in technology or social attitudes. Some issues are highly controversial, like the proposals for the Stonehenge World Heritage sites. Others challenge long-held popular myths, like the deconstruction of the Celts and by extension the Picts. (...) Yet some traditional tenets of scholarship have gone unchallenged for too long, like the classical definition of civilization itself. But why should it matter? Surely it is in the order of things that each generation rejects received wisdom and adopts ideas that are radical or might offend previous generations? Is this not simply symptomatic of healthy and vibrant debate? Or are there grounds for believing that current changes are of a more disquieting character, denying the basic assumptions of rational argument and freedom of enquiry and expression that have been the foundation of western scholarship since the eighteenth century Enlightenment? Re-writing History addresses contemporary concerns about information and its interpretation, including issues of misinformation and airbrushing of politically-incorrect history. Its subject matter is the archaeology of prehistoric and early historic Britain, and the changes witnessed over two centuries and more in the interpretation of the archaeological heritage by changes in the prevailing political and social as well as intellectual climate. Far from being topics of concern only to academics in ivory towers, the way in which seemingly innocuous issues such as cultural diffusion or social reconstruction in the remote past are studied and presented reflects important shifts in contemporary thinking that challenge long-accepted conventions of free speech and debate. (shrink)

We exhibit a 10-element semigroup Q such that the question Does a given quasi-identity hold in Q? is co-NP-complete while the question Does a given identity hold in Q? can be answered in linear time.

We exhibit a 10-element semigroup Q such that the question “Does a given quasi-identity hold inQ?” is co-NP-complete while the question “Does a given identity hold inQ?” can be answered in linear time.

Sandra Harding here develops further the themes first addressed in her widely influential book, The Science Question in Feminism, and conducts a compelling analysis of feminist theories on the philosophical problem of how we know what we ...

This essay is a critical review of Sandra Harding's The Science Question in Feminism. Her text constitutes a monumental effort to capture an overview of recent feminist critique of science and to develop a feminist dialectical and materialist conception of the history of masculinist science. In this analysis of Harding's work, the organizing categories as well as the main assumptions of the text are reconstructed for closer examination within the context of modern feminist critique of science and feminist theory in (...) general. Although a postive review of Harding's text is presented, questions are raised concerning the adequacy of socialist feminist assumptions for such a project, the limitations of Harding's theorization of gender, and the appropriateness of "postmodernism" as a final category of residence. (shrink)

In the mid-1970s and early 1980s, several feminist theorists began developing alternatives to the traditional methods of scientific research. The result was a new theory, now recognized as Standpoint Theory, which caused heated debate and radically altered the way research is conducted. The Feminist Standpoint Theory Reader is the first anthology to collect the most important essays on the subject as well as more recent works that bring the topic up-to-date. Leading feminist scholar and one of the founders of Standpoint (...) Theory, Sandra Harding brings together the a prestigious list of scholars--Dorothy Smith, Donna Haraway, Patricia Hill Collins, Nancy Hartsock and Hilary Rose--to not only showcase the most influential essays on the topic but to also highlight subsequent developments of these approaches from a wide variety of disciplines and intellectual and political positions. The Reader will be essential reading for feminist scholars. (shrink)

Despite its centrality in the philosophy of cognitive science, there has been little prior philosophical work engaging with the notion of representation in contemporary NLP practice. This paper attempts to fill that lacuna: drawing on ideas from cognitive science, I introduce a framework for evaluating the representational claims made about components of neural NLP models, proposing three criteria with which to evaluate whether a component of a model represents a property and operationalising these criteria using probing classifiers, a popular analysis (...) technique in NLP (and deep learning more broadly). The project of operationalising a philosophically-informed notion of representation should be of interest to both philosophers of science and NLP practitioners. It affords philosophers a novel testing-ground for claims about the nature of representation, and helps NLPers organise the large literature on probing experiments, suggesting novel avenues for empirical research. (shrink)

In _Sciences from Below_, the esteemed feminist science studies scholar Sandra Harding synthesizes modernity studies with progressive tendencies in science and technology studies to suggest how scientific and technological pursuits might be more productively linked to social justice projects around the world. Harding illuminates the idea of multiple modernities as well as the major contributions of post-Kuhnian Western, feminist, and postcolonial science studies. She explains how these schools of thought can help those seeking to implement progressive social projects refine their (...) thinking to overcome limiting ideas about what modernity and modernization are, the objectivity of scientific knowledge, patriarchy, and Eurocentricity. She also reveals how ideas about gender and colonialism frame the conventional contrast between modernity and tradition. As she has done before, Harding points the way forward in _Sciences from Below_. Describing the work of the post-Kuhnian science studies scholars Bruno Latour, Ulrich Beck, and the team of Michael Gibbons, Helga Nowtony, and Peter Scott, Harding reveals how, from different perspectives, they provide useful resources for rethinking the modernity versus tradition binary and its effects on the production of scientific knowledge. Yet, for the most part, they do not take feminist or postcolonial critiques into account. As Harding demonstrates, feminist science studies and postcolonial science studies have vital contributions to make; they bring to light not only the male supremacist investments in the Western conception of modernity and the historical and epistemological bases of Western science but also the empirical knowledge traditions of the global South. _Sciences from Below_ is a clear and compelling argument that modernity studies and post-Kuhnian, feminist, and postcolonial sciences studies each have something important, and necessary, to offer to those formulating socially progressive scientific research and policy. (shrink)

For twenty years, the renowned philosopher of science Sandra Harding has argued that science and technology studies, postcolonial studies, and feminist critique must inform one another. In The Postcolonial Science and Technology Studies Reader, Harding puts those fields in critical conversation, assembling the anthology that she has long wanted for classroom use. In classic and recent essays, international scholars from a range of disciplines think through a broad array of science and technology philosophies and practices. The contributors reevaluate conventional accounts (...) of the West’s scientific and technological projects in the past and present, rethink the strengths and limitations of non-Western societies’ knowledge traditions, and assess the legacies of colonialism and imperialism. The collection concludes with forward-looking essays, which explore strategies for cultivating new visions of a multicultural, democratic world of sciences and for turning those visions into realities. Feminist science and technology concerns run throughout the reader and are the focus of several essays. Harding provides helpful background for each essay in her introductions to the reader’s four sections. Contributors Helen Appleton Karen Bäckstrand Lucille H. Brockway Stephen B. Brush Judith Carney Committee on Women, Population, and the Environment Arturo Escobar Maria E. Fernandez Ward H. Goodenough Susantha Goonatilake Sandra Harding Steven J. Harris Betsy Hartmann Cori Hayden Catherine L. M. Hill John M. Hobson Peter Mühlhäusler Catherine A. Odora Hoppers Consuelo Quiroz Jenny Reardon Ella Reitsma Ziauddin Sardar Daniel Sarewitz Londa Schiebinger Catherine V. Scott Colin Scott Mary Terrall D. Michael Warren. (shrink)

In a recent letter, Dillion et. al (2023) make various suggestions regarding the idea of artificially intelligent systems, such as large language models, replacing human subjects in empirical moral psychology. We argue that human subjects are in various ways indispensable.

According to a view assumed by many scientists and philosophers of science and standardly found in science textbooks, it is controlled ex perience which provides the basis for distinguishing between acceptable and unacceptable theories in science: acceptable theories are those which can pass empirical tests. It has often been thought that a certain sort of test is particularly significant: 'crucial experiments' provide supporting empiri cal evidence for one theory while providing conclusive evidence against another. However, in 1906 Pierre Duhem argued (...) that the falsification of a theory is necessarily ambiguous and therefore that there are no crucial experiments; one can never be sure that it is a given theory rather than auxiliary or background hypotheses which experiment has falsified. w. V. Quine has concurred in this judgment, arguing that "our statements about the external world face the tribunal of sense experience not indi vidually but only as a corporate body". Some philosophers have thought that the Duhem-Quine thesis gra tuitously raises perplexities. Others see it as doubly significant; these philosophers think that it provides a base for criticism of the foundational view of knowledge which has dominated much of western thought since Descartes, and they think that it opens the door to a new and fruitful way to conceive of scientific progress in particular and of the nature and growth of knowledge in general. (shrink)

Providing theoretical and applied analyses of Michel Henry's practical philosophy in light of his guiding idea of Life, this is the first sustained exploration of Henry's practical thought in anglophone literature, reaffirming his centrality to contemporary continental thought. This book ranges from the tension between his methodological insistence on life as non-intentional and worldly activities to Henry's engagement with the practical philosophy of intellectuals such as Marx, Freud, and Kandisky to topics of application such as labor, abstract art, education, political (...) liberalism, and spiritual life. An international team of leading Henry scholars examine a vital dimension of Henry's thinking that has remained under-explored for too long. (shrink)

Where the old objectivity question asked, Objectivity or relativism: which side are you on?, the new one refuses this choice, seeking instead to bypass widely recognized problems with the conceptual framework that restricts the choices to these two. It asks, How can the notion of objectivity be updated and made useful for contemporary knowledge-seeking projects? One response to this question is the strong objectivity program that draws on feminist standpoint epistemology to provide a kind of logic of discovery for maximizing (...) our ability to block might makes right in the sciences. It does so by delinking the neutrality ideal from standards for maximizing objectivity, since neutrality is now widely recognized as not only not necessary, not only not helpful, but, worst of all, an obstacle to maximizing objectivity when knowledge-distorting interests and values have constituted a research project. Strong objectivity provides a method for correcting this kind of situation. However, standpoint approaches have their own limitations which are quite different from the misreadings of them upon which most critics have tended to focus. Unfortunately, historically limited epistemologies and philosophies of science are all we get to choose from at this moment in history. (shrink)

Recent "gender, environment, and sustainable development" accounts raise pointed questions about the complicity of Enlightenment philosophies of science with failures of Third World development policies and the current environmental crisis. The strengths of these analyses come from distinctive ways they link androcentric, economistic, and nature-blind aspects of development thinking to "the Enlightenment dream." In doing so they share perspectives with and provide resources for other influential schools of science studies.

Appearing in the feminist social science literature from its beginnings are a series of questions about methodology. In this collection, Sandra Harding interrogates some of the classic essays from the last fifteen years in order to explore the basic and troubling questions about science and social experience, gender, and politics.